10176

# 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 .

### 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.

### PERMANENT CITATION

 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 » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.
 © 2015 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS
 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+