9887

Quantum Circuit Implementing Grover's Search Algorithm

The search problem is formulated as follows: some -bit integer is hidden in a black-boxed subroutine that indicates, when presented with any -bit integer , whether or not coincides with , returning this information as the value of the -bit binary function. The function is implemented by the quantum circuit bounded by two dashed lines in the diagram. The problem is to find in a minimum number of applications of the subroutine.
This Demonstration shows a quantum circuit implementing Grover's search algorithm that enables finding any given integer from the list , where , with a probability that is very close to 1, repeating Grover's iterations times, where is the integer part of the number .

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Snapshot 1: Let a quantum memory register contain four qubits ): three qubits are originally prepared in the state |0〉 and one ancillary qubit is in the state |1〉. Applying four Hadamard gates, one for each qubit, we obtain the equal superposition of all basis states of the four-qubit system. A quantum search subroutine bounded by two dashed lines in the diagram is a 3-bit binary function that outputs 1 if its input is some given integer, for example, and 0 otherwise. This subroutine together with a quantum circuit drawn on the right of the dashed line form one Grover's iteration. The plot shows that after one iteration the probability of getting 5 as a result of measurement in the computational basis is equal to 88 percent.
Snapshot 2: The diagram demonstrates how the quantum circuit changes when one more Grover's iteration is added . After a second Grover's iteration a standard measurement in the computational basis gives 5 with probability 97 percent.
Snapshot 3: We do not add the third iteration in the diagram to avoid drawing a large quantum circuit; one can easily imagine how it will look. But after three iterations the probability of getting the correct result decreases to 57 percent. Thus, the maximum probability of getting the correct result is reached if the number of iterations is equal to its optimal value, which is determined as the integer part of . For large values of this number is .
Similar simulations can be made for or qubits and different possible hidden items . In all cases one can see that the optimal number of Grover's iterations gives the correct result with high probability. For a larger number of qubits the corresponding quantum circuits look similarly but calculations become more cumbersome and require more time. It should be emphasized that a similar search with a classical computer requires applications of the subroutine while a quantum computer gives a quadratic speed-up.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+