microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
samples/OpenQASM/Grover.qasm
92lines · modeblame
88f1a046DmitryVasilevsky1 years ago | 1 | // OpenQASM Grover's Search Algorithm |
| 2 | // | |
| 3 | // Grover's search algorithm is a quantum algorithm that finds with high | |
| 4 | // probability the unique input to a black box function that produces a | |
| 5 | // particular output value. | |
| 6 | // | |
| 7 | // This program implements the Grover's algorithm for one specific function. | |
| 8 | | |
| 9 | OPENQASM 3; | |
| 10 | include "stdgates.inc"; | |
| 11 | | |
| 12 | // Define the number of qubits. It must be 5 for this example. | |
| 13 | const int nQubits = 5; | |
| 14 | // Optimal number of iterations for 5 qubits | |
| 15 | int iterations = 4; | |
| 16 | | |
| 17 | // Given a register in the all-zeros state, prepares a uniform | |
| 18 | // superposition over all basis states. This is a self-adjoint operation. | |
| 19 | def PrepareUniform(qubit[nQubits] qs) { | |
| 20 | for int i in [0:nQubits-1] { | |
| 21 | h qs[i]; | |
| 22 | } | |
| 23 | } | |
| 24 | | |
| 25 | // Reflects about the basis state marked by alternating zeros and ones. | |
| 26 | // This operation defines what input we are trying to find in the search. | |
| 27 | def ReflectAboutMarked(qubit[nQubits] qs, qubit aux) { | |
| 28 | // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that | |
| 29 | // toggling it results in a (-1) phase. | |
| 30 | x aux; | |
| 31 | h aux; | |
| 32 | // Flip the outputQubit for marked states. | |
| 33 | // Here, we get the state with alternating 0s and 1s by using the X | |
| 34 | // operation on every other qubit. | |
| 35 | for int i in [0:2:nQubits-1] { | |
| 36 | x qs[i]; | |
| 37 | } | |
| 38 | // Controlled-X operation | |
| 39 | ctrl(nQubits) @ x qs[0], qs[1], qs[2], qs[3], qs[4], aux; | |
| 40 | | |
| 41 | // Undo the flips | |
| 42 | for int i in [0:2:nQubits-1] { | |
| 43 | x qs[i]; | |
| 44 | } | |
| 45 | h aux; | |
| 46 | x aux; | |
| 47 | } | |
| 48 | | |
| 49 | // Function to reflect about the uniform superposition | |
| 50 | def ReflectAboutUniform(qubit[nQubits] qs) { | |
| 51 | // Transform uniform superposition to all-zero | |
| 52 | PrepareUniform(qs); | |
| 53 | | |
| 54 | // Transform all-zero to all-ones | |
| 55 | for int i in [0:nQubits-1] { | |
| 56 | x qs[i]; | |
| 57 | } | |
| 58 | | |
| 59 | // Reflect about all-ones | |
| 60 | ctrl(nQubits-1) @ z qs[0], qs[1], qs[2], qs[3], qs[4]; | |
| 61 | | |
| 62 | // Undo transformations | |
| 63 | for int i in [0:nQubits-1] { | |
| 64 | x qs[i]; | |
| 65 | } | |
| 66 | | |
| 67 | // Transform all-zero back to uniform superposition | |
| 68 | PrepareUniform(qs); | |
| 69 | } | |
| 70 | | |
| 71 | // Main program | |
| 72 | | |
| 73 | // Allocate qubits | |
| 74 | qubit[nQubits] qs; | |
| 75 | qubit aux; | |
| 76 | // The state we are looking for is returned after execution. | |
| 77 | output bit[nQubits] results; | |
| 78 | | |
| 79 | // Reset the qubits to the |0⟩ state before use. | |
| 80 | reset qs; | |
| 81 | reset aux; | |
| 82 | | |
| 83 | // Prepare uniform superposition | |
| 84 | PrepareUniform(qs); | |
| 85 | | |
| 86 | for int i in [1:iterations] { | |
| 87 | ReflectAboutMarked(qs, aux); | |
| 88 | ReflectAboutUniform(qs); | |
| 89 | } | |
| 90 | | |
| 91 | // Measure the qubits | |
| 92 | results = measure qs; |