Quantum Computing: Algorithms, Qubits, and Gates

Quantum Computing: 3-qubit Grover s Algorithm On IBM Q Eric Li, Dr. Tzu-Chieh Wei, Maziar Farahzad

Quantum Computer Computers which exploit quantum mechanics to do computations IBM Q Commercially available universal quantum computers Open to public access through IBM Composer and QISKit Multiple quantum computers available

qubit Quantum bit Can be 0 , |1 , or a superposition of |0 and |1 quantum superposition The qubit is both |0 and |1 Schr dinger s Cat en.wikipedia.org/wiki/Schr dinger%27s_cat

Bloch Sphere Equation for qubit ? 2 ? 2 ???|1 ? = cos 0 + sin X-axis Y-axis 1 1 + = 0 + 1 ) = 0 + ? 1 ) 2 2 1 1 = 0 1 ) = 0 ? 1 ) 2 2 en.wikipedia.org/wiki/Bloch_sphere

entanglement. a correlation between individually random behaviors of the two particles (IBM Q FAQ) Along with superposition, these two quantum phenomena are the reason why quantum computers have so much potential

Quantum Logic Gates X: 0 1 H: 0 + 1 0 1 1 0 1 1 1 1 2 Z: + CX: 01 01 ; 10 11 (CNOT) 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 CZ: 0 + 0 + ; 1 + 1 CCX: 000 000 ; 100 100 ; 110 111 (Toffoli) 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1

Quantum Matrices ????? The values correspond with the amplitudes of the corresponding basis ? ? ? ? ??? 000 001 010 011 100 101 110 111 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 000 001 010 011 100 101 110 111 00 01 10 11 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 00 01 10 11 0 1 1 0 0 1

Grovers Algorithm ?( ? )in contrast to classical search algorithm s: ?(?) Searching for item in a list of N items Equal amplitude of each value (regardless of solution or non- solution) Uses oracle and inversion about mean to increase the amplitude of solution (which increases its probability) and decrease amplitude of non-solutions www.researchgate.net/figure/Geometric- representation-of-Grovers-search- algorithm_fig1_322243277 quantumexperience.ng.bluemix.net/proxy/tutorial/full-user- guide/004-Quantum_Algorithms/070-Grover's_Algorithm.html

Oracle Marks the amplitude of negative Takes |? to O|? For example, for 2-qubit Grover s Algorithm, finding 11 : 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 CZ = www.researchgate.net/figure/Geometric- representation-of-Grovers-search- algorithm_fig1_322243277 quantumexperience.ng.bluemix.net/proxy/tutorial/full-user- guide/004-Quantum_Algorithms/070-Grover's_Algorithm.html

Inversion About Mean Takes O|? to G|? Formula: 2 ? ?| ? Decomposed: ? ?2 0 0 ?)? ? 2 0 0 ?) = www.researchgate.net/figure/Geometric- representation-of-Grovers-search- algorithm_fig1_322243277 quantumexperience.ng.bluemix.net/proxy/tutorial/full-user- guide/004-Quantum_Algorithms/070-Grover's_Algorithm.html

Oracle for 00 , 01 , and 10 Use X-gates to adjust the CZ gate: As of now, CZ gate marks the amplitude of 11 negative Add X-gates before and after CZ gate to adjust which amplitude it marks negative Marks the amplitude of 00 negative The double X gates map 00 to 11 The amplitude of this 11 is marked negative This 11 is then mapped back to 00 with its amplitude now negative 10marked negative 01marked negative

Number of Iterations Each Grover iteration rotates the original vector |? closer to the solutions axis by a certain angle ? But, how many iterations are required to get it to the solutions axis? Well, most of the time, |? can be rotated very close to ? but not directly onto it With the exception of the 2-qubit algorithm; one rotation takes ? directly to |? The formula for the max number of iterations, R, is ? ?, where N is the total number of items and M is the number of solutions. It can be more precisely calculated with ? = arcsin(2 ? ? ? ? ) ? 4 www.researchgate.net/figure/Geometric- representation-of-Grovers-search- algorithm_fig1_322243277 ? Formulas from the book: Quantum Computation and Quantum Information by Nielsen and Chuang

3-qubit Implementation 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 Relatively simple due to CCZ gate Decomposed into a Toffoli gate with Hadamard gates around target qubit 1 Inversion about mean can be extended to 3-qubit ? ?2 0 0 ?)? ?

2 Lucky Number: 2 ? ? ? ? 2 1 8 1 8 Calculating ? = arcsin = arcsin = 41.41 Starting angle: ? 2= 20.7 Closest to 90 is with two Grover iterations (103.5 )

Simulation Results Perfect results on simulator Extremely high probability of 111

Results on IBM Q 16 Rueschlikon Difficult for results to be worse Random probability of 111 Looks very much like random noise (environmental disturbances)

Initial Debugging Ran the circuit multiple times on IBM Q Each one just as bad Posted the issue to GitHub The Toffoli gate (CCX) is not native to QISKit (package to access IBM Q) Implemented using 6 CX gates which have a decently high amount of error I had four Toffoli gates total Suggested that I reduce the number of 2-qubit gates and run on IBM Q 5 Tenerife (lower error rates)

Resolving the Issue Needed a better Toffoli gate Decomposed CCZ gate (which I could replace the H-Toffoli-H) gate using 3 CU gates and 2 CX gates But the CU gates (control unitary phase shift gates) are implemented using two-qubit gates Would introduce more error as more two-qubit gates are being used Lower the number of 1-qubit gates H-X-H = Z Only run one iteration Run on IBM Q 5 Tenerife

Results on IBM Q 5 Tenerife Not ideal but not horrendous Decently high probability of 111 relative to others