Quantum algorithms

A quantum algorithm can be seen as the controlled time evolution of a physical system obeying the laws of quantum mechanics. It is therefore of utmost importance that each qubit may be coherently manipulated, between arbitrary superpositions, via the application of external stimuli. Furthermore, all these manipulations must take place well before its quantum wave function, thus the information it encodes, is corrupted by the interaction with external perturbations. The need to properly isolate qubits but, at the same time, to rapidly... 

Of interest to us is that quantum computers add a completely new class to this hierarchy the class of non-deterministic algorithms that can be solved in polynomial time on a quantum computer, so-called BQP [Bernstein 1997], The key to these fantastic quantum algorithms, or so everybody believed until recently, was the presence of in these systems. 

Theorem Pure-state quantum algorithms may be efficiently simulated classically, provided there is a bounded amount of global entanglement. 

We shall ask whether Grover s quantum algorithm for solving this problem on an entanglement-free pseudo-pure state based machine can offer any speedup over classical performance. The key feature of Grover s algorithm for a pure-state implementation is that at step k the quantum computer is in state... 

After Benioff, in the year of 1985, David Deutsch gave a decisively important step towards quantum computers presenting the first example of a quantum algorithm [6]. The Deutsch algorithm shows how quantum superposition can be used to speed up computational processes. Another influent name is Richard Feynman, who was involved about the same time in the discussions of the viability of quantum computers and their use for quantum systems simulations [7]. 

However, it was in 1994 that a main breakthrough happened, calling the attention of the scientific community for the potential practical importance of quantum computation and its possible consequences for modem society. Peter Shor discovered a quantum algorithm capable of factorizing large numbers in polynomial time [8]. Classical factorization is a kind of problem considered by computation scientists to be of exponential complexity. 

J.A. Jones, M. Mosca, Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer, J. Chem. Phys. 109 (1998) 1648. 

David Deutsch creates the first quantum algorithm. 

The most important quantum algorithm, the Shor algorithm [11], uses the QFT for finding the order of a number, which increases the speed of the factorization process. These are basically implemented by the same quantum circuit and are the main reasons for the exponential gain of speed in comparison with the classical factorizing algorithm. 

Perhaps, the most striking aspect of quantum computation are the quantum algorithms, which can compute states of bit sequences that are impossible for classical computers, such as superposition and entangled states. Here lies the power of the quantum algorithms. 

Quantum algorithms can be divided into two classes, called A and B, the exponentially fast and the polynomially fast, respectively. 

R. Jozsa, Quantum algorithms and the Fourier transform, Proc. Royal Soc. London A 454 (1998) 323. 

A two qubit-gate very used in quantum algorithms is the SWAP gate. It can be directly implemented by the pulses corresponding to three successive CNOT gates. 

---