Introduction

What's the point#

• Better understanding of the foundations and provide more clear intuition about quantum measurement; especially entanglement.
• Efficient computation.
• Cryptography
  • Private key distribution: robust against eavesdropping
  • Public key cryptography: Shor's algorithm can break RSA efficiently. 

Quantum computation and information theory are closely related due to the probabilistic nature of quantum mechanics: Analog computation has the possibility of violating the strong form (computational complexity version) of the Church-Turing thesis, but when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances. The development of a theory of quantum error-correcting codes and fault-tolerant quantum computation takes into account of the effects of realistic noise. In principle, unlike analog computation, quantum computation can tolerate a finite amount of noise and still retain its computational advantages.

Efficient computation#

What's a quantum computer good for? It enables new algorithms which render feasible problems requiring exorbitant resources for their solution on a classical computer. For now, two broad classes of quantum algorithms:

• Quantum Fourier transform: includes remarkable algorithms for solving the factoring and sicrete logarithm problems, providing an exponential speedup over the best known classical algorithms. Hence breaking many popular cryptosystems now in use.
• Quantum searching: provide quadratic speedup over the best possible classical algorithms. This provides speed up for some NP problems.