Category: Quantum Algorithms

Some texts implement the quantum function evaluator as a “controlled- ˜ U f ” gate (Figure 8.19), where ˜ U f acts only on the lower register, and is defined by ˜ U f |yi = |y ⊕f(x)i: |xi • |xi |yi ˜ U f |y ⊕ f(x)i FIGURE 8.19: The quantum function evaluator as…

A simple extension to this algorithm works when the search criterion has multiple solutions. The oracle then gives an answer “yes” whenever any one of the M possible solutions is input. The Hilbert space then has a “solution subspace” M, spanned by M solution states. Let us denote by |βi the uniform superposition of all…

Another famous algorithm that made a splash in the world of quantum computing was invented by L. K. Grover in 1997 [40]. This algorithm is in a different class from the ones we have studied so far, which may all be said to be QFT-based. Grover’s algorithm introduced a new technique: amplitude amplification. Even though…

estimation One version of Shor’s algorithm is based on phase estimation. This appli- cation of the quantum Fourier transform is used to estimate the eigenvalue of a unitary operator, which is a phase: ˆ U|ui = e iθ |ui; θ = 2πφ (8.63) where φ is a fraction. As a preliminary to this algorithm, let’s…

The quantum Fourier transform (QFT) is simply the DFT operation on the amplitudes of a quantum state. The DFT matrix is unitary, and can therefore represent a quantum transformation. We can define the QFT (order N = 2 n ) of an n-qubit basis state |xi by ˆ F N |xi = 1 √ N…

Applications The Fourier transform, a mathematical tool named after the 18th century French mathematician Joseph Fourier, is an invaluable tool in engineering and the sciences. No technical education is complete without a firm grasp of this technique and its uses. The simplest way to understand the Fourier transform F of a function f (x) is…

Even though the Bernstein–Vazirani algorithm offers such a great speedup, the classical solution is still not exponential. Daniel Simon came up with an algorithm [65] in 1994 that is the first to demonstrate a dramatic exponential speedup over a hard classical problem, but the solution is probabilistic. This feature is characteristic of many quantum algorithms.…

We’ll now look at algorithms that show more substantial speedups com- pared to classical ones. One such algorithm was invented by Umesh Vazirani and his student Ethan Bernstein in 1993 [11]. This algorithm identifies a linear Boolean function in one query of the oracle. The problem: given a function evaluator for f : {0, 1}…

Let’s start with 1-bit functions f : {0, 1} 7→ {0, 1}. There are totally four possible functions, and evaluated on inputs 0 and 1 can give answers 0 or 1. To actually determine which of these our black box is we need to query it with both inputs, whether classically or otherwise, and we…

The advantage of the quantum function evaluator is that it can take all possible inputs simultaneously as a superposition of states, and the corre- sponding outputs are all simultaneously present in the output state. This has often been called quantum parallelism. However, in this basic form it gives us no advantage, since to actually discover…