Brute-force is apparently applicable to any problem of NP, since if you have some candidate for an answer, you can easily check / verify this candidate (but finding a candidate is still hard).
For example: given a phone number to find its owner in the phone book, you can easily check it, but you need n/2 time to find it on average. Another example is the traveling salesperson problem, where you don’t have the path but only desired length, finding the path is complicated, in the worst case you need n! time where n is the number of vertices.
For any problem that is solvable by brute-force search, if you can speed up the brute-force search with a quantum computer, you can make the process more effective. Lov Grover dealt with quantum algorithm which is able to solve any problem of NP, independent of its structure.
Grover’s Algorithm
Consider the phone book problem, where owners’ names are arranged in alphabetized order, it is easy to find the phone number given a name. This could be formalized as a function f: {0,1}n → {0,1}n, there exists ω (a name) in the domain, such that f(ω) = a, where a is the phone number. Having f(ω) defined, we could further define another function fω(x) = δx=ω, which maps n-bit integer to 1 bit:
fω(x ≠ ω) = 0
fω(x = ω) = 1In quantum computing, the function fω is defined as an operator Uf as usual:
Uf|x⟩|y⟩ = |x⟩|y ⊕ fω(x)⟩If we pass through the |y⟩ register the Hadamard |-⟩, we have this express as usual:
Uf 1/√2 |x⟩(|0⟩-|1⟩)
= 1/√2 |x⟩(|0 ⊕ fω(x)⟩ - |1 ⊕ fω(x)⟩)
= 1/√2 (-1)fω(x) |x⟩(|0⟩ - |1⟩)We only consider the projection Uω|x⟩ = (-1)fω(x) |x⟩, which works like below:
∀ |x⟩ ≠ |ω⟩ Uω|x⟩ = |x⟩
∀ |x⟩ = |ω⟩ Uω|ω⟩ = -|ω⟩Actually, the Uω|x⟩ operator can be rewritten like this:
Uω|x⟩ = I - 2|ω⟩⟨ω|The input data of the Grover’s algorithm is |s⟩ = H|0⟩n = 1/2n/2 Σ2^n-1x=0 |x⟩, here we can define another useful operator:
Us = 2|s⟩⟨s| - IEach iteration of the Grover’s algorithm is: Rgrov = Us Uω. After applying k iterations on initial state |s⟩, we have something like this: (Us Uω)k |s⟩.
|ω⟩ is a vector in the space with dimensionality N. |s⟩ = 1/√N ∑N−1x=0 |x⟩. The sine of the angle θ between |s⟩ and the hyperplane which is orthogonal to |ω⟩, is sin(θ) = 1/√N.
Each iteration of Grover’s algorithm makes us closer to the state |ω⟩ with each step 2θ. Suppose we have made T iterations, T ≈ (π/4)√N. The time need to find a solution is O(√N).
Why we choose the vector |s⟩ as an initial state? |s⟩ has equal angles to all the basis vectors of the space. We don’t know anything about |ω⟩, but we must know θ.
When there are multiple ωi, such that fω(ωi) = 1, 1 ≤ i ≤ k . The algorithm does not change, but we have k vectors, and angle θ becomes greater. The sine of the angle θ between |s⟩ and the hyperplane which is orthogonal to all vectors |ωi⟩, is now sin(θ) = √k/√N. And T ≈ (π/4)*(√N/√k).
Note that to use Grover’s algorithm, we must know the number of special points k to calculate the number of iterations T. Grover’s algorithm does not tolerate extra work. If you do more iterations than it’s needed, we may pass this point of interest.
The reason we choose operator Us is because it reflect in the desired direction. |s⟩ is the only thing we know in this space, i.e. the equally weighted sum of all basis vectors.
Optimality
Lov Grover proved that there is no better algorithm than Grover’s algorithm. Suppose:
- The target is
|ω⟩. - There exist, in general, some operator better:
U(ω,t) = UtUωUt-1Uω...U1Uω. Here Ut is the generalization of Us in Grover’s algorithm. |ψ0⟩is the initial state.|ψt⟩ = U(ω,t)|ψ0⟩- T is defined as
U(ω,t)|ψ0⟩ = |ψT⟩ = |ψω⟩ ≈ |ω⟩ - We are going to find some vector
|ϕ⟩for which this double inequality is true:
4T2 ≥ ∑N-1ω=0 || |ψω⟩ - |φ⟩ ||2 ≥ 2N - 2√N
⟹ 4T2 ≥ 2N - 2√N
⟹ T ≈ √N/√2Compare the T with that of Grover’s algorithm (Tgrov = (π/4)√N). The most effective algorithm is not very much better than that of Grover’s.
Quantum Computers aren’t Always Better
Quantum computers are not always better than classical ones. There are problems on which the quantum computers are almost as ineffective as classical ones.
Let’s consider all the functions of type f(x): {0,1}n → {0,1}, and for any such functions, we could introduce the value x = xN-1xN-2...x0, N = 2n, which is a very long bit string.
Function Parity() maps functions to 1 bit. First each bit xi is used to calculate x~i, then parity is calculated:
x~i = 1 - 2xi
Parity(x~) = ∏N-1i=0 x~iIf there are even numbers of 1 in x, the parity is 1; if there is odd number of 1 in x, the parity is -1.
To calculate the parity of a function of type f(x): {0,1}n → {0,1}, in classical computing, we have to try all the function values and multiply them. However quantum computer can not outperform classical ones on this task.
My Certificate
For more on Grover’s Algorithm, please refer to the wonderful course here https://www.coursera.org/learn/quantum-computing-algorithms
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
