Scribd
Upload
52 views

Shor's Algorithm

Uploaded by

Satheesh Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
52 views

Shor's Algorithm

Uploaded by

Satheesh Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 7
Shor’s Quantum Prime Factorization Algorithm Satheeshkumar S 34322017Shor’s Algorithm + Itis the quantum factorization algorithm and it reduce the time complexity of exponential time to polynomial time. (a3 +1)(a3 -1)=mxN + N = Composite prime number (source) + a=arandom guess & m = an integer + r = an even number we need to find (target) + Procedure + Guess a and find ged(a, N).If it is 1, it is a solution + Otherwise, Substitute in above equation and find r + Ifr is even, find ged(N, (a3 + 1)) + Ifris odd, repeat the procedure ...Quantum Version of Shor’s Algorithm + All the qubits are undergo superposition by applying H Gate to get all possible solution simultanously. The modulo exponentiation is defined in quantum by an operator U and it is act on qubit with initial state |1) Uly) = |aymod N) Repetatedly applying U gate leads to get the qubit to the own state |1), here we just find the phase which is change by U operator. And that is the r. UT ly) = |) Our goal is to find & from & = §, § is a random integer. Finally, Applying Quantum Fourier Transform Inverse Gate to the qubits. + When we measure repeatedly we can get the probable state.Quantum Computing Quantum Computing can be done by constructing quantum circuit. Quantum Circuit has three important thing. 1. State : |0) and |1) are represented by a Qubit. + Qubits are represented by the spin of the electron. + Can have the property like Superposition and Entanglement, 2. Operator : Every quantum operator is represented as a Gate. + Every Gate is reversible in Quantum Computing. + The Operation on qubit is denoted in a bloch sphere. + Example: H, X,Y, Z,1,CX, 8, S* 3, Measurement : Even though the qubit is in superposition, after measurement it collaped to either one of the state.Quantum Circuit of Shor’s Algorithm of of 8 of ofResult 240 féédé + In this case, N = 15 anda =7. + And we can find the result 11000000(bin) which is 3(dec) as one of the solution. + we can find other prime number by just dividing it ¥ (3 x 5 = 15)Thank You Reference : https:/learning.quantum ibm.com/course/fundamentals-of-quantum- algorithms/phase-estimation-and-factoring#shors-algorithm

You might also like