A "decision problem" can be modelled as :
A resource independent way of quantifying the hardness of a problem is to analyse how the size of a circuit scales with the input size $n$. The above problem scales exponentially ($2^n$) with input size $n$.
We say that a decision problem is in $P$ if the algorithm (or circuit family) can be described as a polynomial function of input size $n$. As a matter of fact, most of the functions described by the above mapping are not in $P$. For such functions, the only way to determine $f(x)$ is to search a table for the solution out of exponentially many possible entries. This table can be considered as the digital equivalent of a haystack, and the solution to the problem is a needle which we are interested in finding. Hence finding a solution to an NP-complete [a] problem can be seen as a search problem represented by the following Boolen satisfiability [b].
The satisfiability problem is to find a configuration $x_1, x_2, x_3, ..., x_n$ such that $f(x_1, x_2, x_3, ..., x_n) = 1$. It is clear that the problem requires us to look up a haystack of $2^n$ entires and find a needle. In fact there are thousands of NP-complete problems which are computationally equivalent to satisfiability. The problems in P are the ones which have enough structure in them to be computationally easy to solve.
[b] The Boolean satisfiability is a part of Cook's Theorem (1971), which states that every problem in NP is polynomially (in input/circuit family) reducible to CIRCUIT-SAT.
# Setup the matplotlib graphics library and configure it to show
# figures inline in the notebook
%matplotlib inline
import matplotlib.pyplot as plt
# Import Numpy arrays
import numpy as np
# Setup Ipython to load local images
from IPython.display import Image
import pprint
Quantum Fourier Transform (QFT) or Fourier Sampling is the quantum analogue of the Discrete Fourier Transform (DFT) [10]. Most Quantum Algorithms derive their exponential speed by virtue of QFT. QFT lets us define a state in a new computational basis. From a Physics point of view, the relationship between the two bases is analogous to that between the momentum and position bases of a particle. The mathematical representation of DFT is:
The Quantum Fourier Transform is applied on the above state as:
It is clear that Discrete Fourier Transform (DFT) is performed on the amplitudes of the quantum state, through a linear transformation. The $F$ operator can be written in outer product notation as:
The $F$ operator in matrix form is as follows:
In general we see that the matrix for Quantum Fourier Transform has the form:
Two-Qubit QFT in matrix form:
Note that the QFT matrix is a unitary operator since $F F^\dagger = F^\dagger F = I$
To calculate $\beta_0$ time required = O(N)
To calculate $\beta_1$ time required = O(N)
Hence an ordinary algorithm (or a human) would take O($N^2$) steps to compute the Fourier Transform of a state.
The Fast Fourier Transform (FFT) algorithm (or [Cooley-Tuckey algorithm]) is a classical algorithm which can compute the DFT of a vector in O($N \log {N}$) steps.
The Quantum Fourier Transform (QFT) takes O($n^2$) steps at maximum.
Hence the computational complexity of performing a QFT is:
We know, any binary fraction can be written as $\sum\limits_{l=1}^{n} k_l 2^{-l}$
We can break the $2^n$ terms in the summation and replace it by $n$ summations over an $n$-bit binary string.
$n$ summation terms can be grouped to one by tensoring it $n$ times.
We can represent $j2^{-l}$ as a binary fraction. Thus the resulting equation is:
Problem Definition:
In mathematical terms, the problem of unstructured search can be defined by the following quantum oracle.
We are given a database with $N$ records labelled as $0, 1, 2, \cdots, N-1$. We assume $N=2^n$ for the simple reason of storing each index in $n$ bits. Rather than dealing with list itself, we focus on the index of the list. The oracle is thus the following binary function with an $n$-bit binary string input.
Example:
There are many problems which can be rephrased as a search problem. One practical example is the random brute force attack on a Data Encryption Standard (DES) encrypted ciphertext. Assume that the key is a 56-bit number.
P (plaintext) = "BlowUpHRI"
The oracle for the above problem would be:
Classical algorithms:
$O(N)$ expcected time with linear search.
$O(\frac{N}{2})$ expected time with random brute force.
$O(\log{N})$ with binary search for databases with structure (sorted).
Quantum algorithm:
Claim is that quantum algorithm for unstructured search will take time $O(\sqrt{N})$. To search a desired element in an unstructured database, a quantum mechanical algorithm will take at least $\Omega(\sqrt{N})$ steps [5]. Hence the number of steps required by Grover's algorithm is within a constant factor of the fastest possible quantum mechanical algorithm.
Worst case:
There is only $x$ such that $f(x) = 1$
Phase Inversion:
The initial state of the system is a uniform superposition of all states. The phase inversion step inverts the sign of the amplitude of the needle ($x^*$).
Reflection about mean:
Algorithm:
The steps 3-5 can be combined into a single unitary transformation $I_s$ such that the net Grover's operator becomes $G=I_s I_t$:
# Helper functions implemented in Python
def U_phase(psi, e):
"""
Unitary transformation to invert the phase of the search element
Parameters | Returns
--------------------------|----------------------------------
psi : ndarray | psi : ndarray
Quantum state | State after phase inversion
e : int |
Search element |
"""
if psi.shape[0] >= e:
psi[e] *= -1
return psi
def QFT(psi, N):
"""
Quantum Fourier Transform operator in N dimensions
Parameters | Returns
--------------------------|---------------------------
psi : ndarray | QFT : ndarray
Quantum state | QFT unitary operator
N : int |
Number of dimensions|
Internals
---------
Makes use of the DFT method of NumPy. QFT is a unitary operator
so the QFT matrix is its own inverse.
"""
return np.fft.fftn(psi)/N**0.5
def Diffusion(N):
"""
Diffusion operator D for Grover's iterations
Parameters | Returns
--------------------------|------------------
N : int | D : ndarray
Number of dimensions| Unitary operator D
"""
return np.ones((N, N)) * 2/N - np.identity(N)
def __iter(N):
"""
Number of iterations to run the Grover's operators
Parameters | Returns
--------------------------|------------------
k : int | N : int
Number of dimensions | Number of Grover iterations
"""
return int(np.floor(np.pi * (N**0.5) /4))
N=4
x=2
psi = np.ones((N, 1))/N**0.5
psi = U_phase(psi, x)
psi = QFT(psi, N) # QFT on state psi
si = np.zeros((N, 1))
si[0][0] = 1 # The |0> state
si_dag = np.conjugate(si.T) # The <0| state
S = 2 * np.kron(si, si_dag) - np.identity(N) # S = (2|0><0|-I)
psi = np.dot(S, psi) # Conditional phase shift operation
psi = QFT(psi, N) # Inverse QFT on state psi
psi
array([[ 0.+0.j], [ 0.+0.j], [ 1.+0.j], [ 0.+0.j]])
N = 256
x = 55
D = Diffusion(N)
k = __iter(N) # Estimate least number of iterations required
probability_amplitude_list = [1/(N**0.5)]
psi = np.ones((N, 1))/N**0.5
for c in xrange(k):
if c==k-1:
fig = plt.figure(figsize=(5, 5))
ax1 = fig.add_subplot(311)
plt.bar(np.arange(N), psi.T[0])
ax1.set_title("Superposition in iteration: %s"%(c+1))
psi = U_phase(psi, x) # Conditional phase shift
ax2 = fig.add_subplot(312)
ax2.set_title("Conditional phase shift")
plt.bar(np.arange(N), psi.T[0])
psi = np.dot(D, psi) # Reflection about mean
ax3 = fig.add_subplot(313)
ax3.set_title("Reflection about mean")
plt.bar(np.arange(N), psi.T[0])
fig.text(0.5, 0.01, 'Database entries', ha='center', va='center')
fig.text(0.01, 0.5, 'Probability amplitude', ha='center', va='center', rotation='vertical')
fig.tight_layout()
probability_amplitude_list.append(psi[x][0])
else:
psi = U_phase(psi, x) # Conditional phase shift
psi = np.dot(D, psi) # Reflection about mean
probability_amplitude_list.append(psi[x][0])
Image("plots.png")
probability_list = [i ** 2 for i in probability_amplitude_list]
fig = plt.figure(figsize=(10, 10))
ax1 = fig.add_subplot(221)
ax1.set_xlabel("Iterations")
ax1.set_ylabel("Probability amplitude")
plt.plot(np.arange(k+1), probability_amplitude_list)
ax2 = fig.add_subplot(222)
ax2.set_xlabel("Iterations")
ax2.set_ylabel("Probability")
plt.plot(np.arange(k+1), probability_list)
print '''Probability amplitudes
----------------------'''
pprint.pprint(probability_amplitude_list)
print '''Probabilities
----------------------'''
pprint.pprint(probability_list)
Probability amplitudes ---------------------- [0.0625, 0.1865234375, 0.3076324462890625, 0.4239346981048584, 0.53361297026276588, 0.63495353976031765, 0.72637296019911446, 0.8064428031348001, 0.87391197727150449, 0.9277262767633413, 0.96704485318074529, 0.99125335376719736, 0.99997352070104339] Probabilities ---------------------- [0.00390625, 0.034790992736816406, 0.094637722009792924, 0.17972062825725743, 0.28474280203265145, 0.40316599765415728, 0.52761767730842435, 0.65034999472791399, 0.76372214401859062, 0.86067604459717173, 0.93517574806336923, 0.98258321135471649, 0.99994704210324004]
Let us consider a database of $N$ items having $M$ solutions.
Thus, the initial superposition can be written as:
Let the rotation brought about by the Grover operator be repeated for $k$ number of times. We are interested in finding the minimum value of this number $k$. The effect of Grover's operator $G$ on the initial state is given below.
[1] Lov K. Grover, "A fast quantum mechanical algorithm for database search", Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 212, 1996 [arXiv.org:quant-ph/9605043]
[2] Lov K. Grover, "Quantum Mechanics helps in searching for a needle in a haystack", Physical Review Letters, Volume 79, Number 2, pp. 325-328, 1997 [arXiv.org:quant-ph/9706033]
[3] Samuel J. Lomonaco Jr., "Grover's Quantum Search Algorithm", Proceedings of Symposia in Applied Mathematics,
[4] Lov K. Grover, "Quantum computer can search arbitrarily large databases by a single query", Physical Review Letters, pp 4709-4712, 1997.
[5] C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, "Strengths and Weaknesses of Quantum Computing", SIAM Journal of Computing, 26, 1510, 1997 [arXiv.org:quant-ph/9701001]
[6] M. A. Neilsen and I. L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000.
[7] Dieter van Melkebeek, "Quantum Search", CS880: Quantum Information Processing, University of Wisconsin-Madison, Fall 2010
[8] Umesh Vazirani, "Quantum Search + Quantum Zeno effect", CS191: Quantum Information, University of California-Berkeley, Spring 2012
[9] "Cooley Tuckey FFT Algorithm" [http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm]
[10] "Discrete Fourier Transform" [http://en.wikipedia.org/wiki/Discrete_Fourier_transform]
[11] "Fastest Fourier Transform in the West" [http://en.wikipedia.org/wiki/FFTW]