Advance Technology and Methods within Finance

So back to a fun topic that seems to have a great following, both by naysayer and sayer alike. There are a number of quantum computing candidates, among those. I have done some preliminary work with the guys at D-Wave and I feel these machines will be very useful tool in financial engineering in the near future. To remind ourselves of what is considered a quantum computer lets look at what vid DiVincenzo, of IBM, listed the following requirements for a practical quantum computer:

• scalable physically to increase the # of qubits
• qubits can be initialized to arbitrary values
• quantum gates faster than decoherence time
• Turing-complete gate set
• qubits can be read easily

There are a number of practical difficulties in building a quantum computer, and thus far quantum computers have only solved trivial problems. One major problem is keeping the components of the computer in a mixed state as the slightest interaction with the external world would cause the system to decohere.

• Superconductor-based quantum computers
• ” Nuclear magnetic resonance on molecules in solution“-based
• ” quantum dot on surface”-based
• ” laser acting on floating ions (in vacuum)”-based ( Ion trapping )
• ” Cavity quantum electrodynamics ” ( CQED )-based
• molecular magnet-based
• SQUID-based
• the solid state NMR Kane quantum computer

This section surveys what is currently known mathematically about the power of quantum computers. It describes the known results from computational complexity theory and the theory of computation dealing with quantum computers.

The class of problems that can be efficiently solved by quantum computers is called BQP, for “bounded error, quantum, polynomial time”. Quantum computers only run randomized algorithms, so BQP on quantum computers is the counterpart of BPP on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one half. A quantum computer is said to “solve” a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.

BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

An operator for a quantum computer can be thought of as changing a vector by multiplying it with a particular matrix. Multiplication by a matrix is a linear operation. It has been shown that if a quantum computer could be designed with nonlinear operators, then it could solve NP-complete problems in polynomial time. It could even do so for #P-complete problems. It is not yet known whether such a machine is possible.

Although quantum computers are sometimes faster than classical computers, they can’t solve any problems that classical computers can’t solve, given enough time and memory. A Turing machine can simulate a quantum computer, so a quantum computer could never solve an undecidable problem like the halting problem. The existence of quantum computers does not disprove the Church-Turing thesis.