CS代考 Quantum Programming Algorithms: Palsberg Feb 3, 2022

Quantum Programming Algorithms: Palsberg Feb 3, 2022

Quantum Programming, by Outline Algorithms: Shor; 100 minutes; Feb 3, 2022
Hook: Shor’s algorithm factors integers in polynomial time with high probability. This creates trouble for RSA cryptography, which relies on that factoring integers is hard. Indeed, part of the promise of quantum computing is that Shor’s algorithm will break some forms of cryptography that are widely used on the Internet. But how does Shor’s algorithm work?

Purpose: Persuade you that you can understand Shor’s algorithm at a high level.
1. Shor’s algorithm consists of a classical algorithm that calls a quantum subroutine. 2. We will present an example run of the algorithm.
3. We will outline how the quantum subroutine works.
Transition to Body: Now let us look at the big picture of factoring integers.
Main Point 1: Shor’s algorithm consists of a classical algorithm that calls a quantum subroutine. [The algorithm is probabilistic and it guesses and checks candidates]
[We use known classical algorithms to isolate the core problem]
[A key subroutine finds the order of an element in a group]
Transition to MP2: This algorithm has many components that are nontrivial.
Main Point 2: We will present an example run of the algorithm.
[We will pick an input that requires more than a little bit of work] [We will make a good guess in the first try]
[We will go through the steps at a high level]
Transition to MP3: And where does quantum come in?
Main Point 3: We will outline how the quantum subroutine works.
[Order finding uses phase estimation as a subroutine]
[Phase estimation uses the quantum Fourier transform as a subroutine]
[The quantum Fourier transform is exponentially faster than the classical FFT]
Transition to Close: So there you have it.
Review: At the core of Shor’s algorithm is a subroutine for finding the order of an element in a
group. This subroutine can be executed efficiently on a quantum computer.
Strong finish: Shor’s algorithm prompted cryptographers to study post-quantum cryptography and it created a lot of excitement about the promise of quantum computing.
Call to action: Find an implementation of Shor’s algorithm in Qiskit, or write it yourself, and run it on IBM’s quantum computer with input 15, and see if you get 3,5.

Detailed presentation
Hook: Shor’s algorithm factors integers in polynomial time with high probability. This creates trouble for RSA cryptography, which relies on that factoring integers is hard. Indeed, part of the promise of quantum computing is that Shor’s algorithm will break some forms of cryptography that are widely used on the Internet. But how does Shor’s algorithm work?
Purpose: Persuade you that you can understand Shor’s algorithm at a high level.
1. Shor’s algorithm consists of a classical algorithm that calls a quantum subroutine. 2. We will present an example run of the algorithm.
3. We will outline how the quantum subroutine works.
Transition to Body: Now let us look at the big picture of factoring integers.
Main Point 1: Shor’s algorithm consists of a classical algorithm that calls a quantum subroutine.
[The algorithm is probabilistic and it guesses and checks candidates]
The idea of Shor’s algorithm is to guess a random integer that is less than the input and then check whether the guess leads to a factoring. The guess-and-check may well fail but it will succeed with probability greater than 12 . So if we repeat the guess-and-check a few times, we are highly likely to succeed.
[We use known classical algorithms to isolate the core problem]
Here is the algorithm for integer factorization. Notice that the algorithm calls itself recursively.
Algorithm: Input: Output: Method:
Integer Factorization.
A positive integer N ≥ 2.
A prime factorization N = pk1 × … × pkm. 1m
if(N=pk wherepisprimeandk≥1){ return pk
if (N is even) {
return combine(2, IntegerFactorization(N2 )) }
int d = Shor(N)
return combine(IntegerFactorization(d), IntegerFactorization(Nd ))
The above algorithm calls Shor’s algorithm as a subroutine, and it is informal about the following three aspects. First, it calls a classical subroutine to check whether N is the power of a prime. Second, it calls a classical subroutine to check whether N is even. Third, it calls a classical subroutine to combine two prime factorizations. Those three subroutines can all be implemented in polynonial time on a classical computer; we skip the details.

Here is Shor’s algorithm.
Algorithm: Input: Output:
Shor’s Algorithm.
An odd, composite integer N that is not the power of a prime. A nontrivial factor of N, that is, anintegerdsuchthat1 1) {
return d }
int r = FindOrder(a,N)
if (r is even) { r
until we give up
intx=a2 −1(modN) int d = gcd(x, N)
if (d > 1) {
return d }
Shor’s algorithm calls the subroutine FindOrder. The idea is that FindOrder(a,N) returns the smallest integer r > 0 such that ar ≡ 1 (mod N). This number r is known as the order of a in Z∗N. Here,ZN ={0,1,…,N−1}andZ∗N = {a∈ZN |gcd(a,N)=1}. IfweequipZ∗N withabinary operation which is multiplication modulo N, then it forms a group.
The idea of Shor’s algorithm is that if we know that the order r of a ∈ Z∗N is even, then we have ar ≡ 1 (mod N)
N | (ar − 1) and since ar −1 = (ar2 +1)×(a2r −1), we have
N|((a2 +1)×(a2 −1)) rr
Notice that N | (a2 −1) is false because otherwise a2 ≡ 1 (mod N), which implies that r is not the
order of a after all, because ar2 ≡ 1 (mod N) and 2r < r, which contradicts that r is the order of a. r So,weletx=a2 −1(modN),andthenwecomputed=gcd(x,N). Ifd>1,thenwehave r
foundanontrivialfactorofN. Butifd=1,thenwehaveN |(a2 +1)andwehadnoluckwitha.
Let us analyze the success rate of the repeat-loop. Each iteration of the loop fails to give an r
answer if either r is odd, or r is even but N | (a 2 + 1). The probability that neither of these events occur is at least 12 when N is an odd, composite integer that is not the power of a prime, which is exactly the precondition for Shor’s algorithm.

[A key subroutine finds the order of an element in a group]
The subroutine FindOrder takes a long time to do on a classical computer. Shor’s insight is that FindOrder can be done efficiently on a quantum computer. Specifically, on a classical computer, FindOrder(a,N) takes time that is polynomial in N. But, on a quantum computer, FindOrder(a,N) takes time that is logarithmic in N.
Transition to MP2: This algorithm has many components that are nontrivial. Main Point 2: We will present an example run of the algorithm.
[We will pick an input that requires more than a little bit of work]
Let us go with N = 21. We can see that N is not the power of a prime and N is not even. So, we call Shor’s algorithm on N.
[We will make a good guess in the first try]
Let us pick a = 2. This pick will lead to a single iteration of the repeat-loop.
[We will go through the steps at a high level] Let us calculate:
d = gcd(a,N) = gcd(2,21) = 1 Now we call FindOrder, and we see that
r = FindOrder(a, N ) = FindOrder(2, 21) = 6, because 26 = 1 (mod 21).
Next we notice that r is even, so we calculate r6
x = a2 −1(modN) = 22 −1(mod21) = 7 d = gcd(x,N) = gcd(7,21) = 7
We see that d is greater than 1, so we return d = 7.
Transition to MP3: And where does quantum come in?
Main Point 3: We will outline how the quantum subroutine works.
[Order finding uses phase estimation as a subroutine]
Algorithm: Input: Output:
Order Finding.
An integer N > 1 and an element a ∈ Z∗N .
The smallest integer r > 0 such that ar ≡ 1 (mod N).
Let n be the number of bits needed to encode an element of Z∗N in binary. Define a unitary operation Ma
Ma|x⟩ = |ax (mod N)⟩ 5

where x ∈ Z and the order of a is r. From now on, we will implicity assume that the operations inside kets are modulo N.
Notice that, for ω = e2πi/r, if
|ψk⟩ = √1 (|1⟩ + ω−k|a⟩ + ω−2k|a2⟩ + . . . ω−(r−1)k|ar−1⟩)
Ma|ψk⟩ = ωk|ψk⟩
Let us check the above by doing a calculation for the case of |ψ1⟩:
so |ψk⟩ is an eigenvector of Ma.
Algorithm: Input: Output:
Phase Estimation.
A unitary operation U and an eigenvector |ψ⟩ of U, that is, U|ψ⟩ = e2πiθ|ψ⟩. θ.
Ma√1 (|1⟩+ω−1|a⟩+ω−2|a2⟩+…+ω−(r−1)|ar−1⟩) r
= √1 (|a⟩+ω−1|a2⟩+ω−2|a3⟩+…+ω−(r−1)|ar⟩)
= √1 (|a⟩+ω−1|a2⟩+ω−2|a3⟩+…+ω−(r−1)|1⟩) r
= √ω (ω−1|a⟩+ω−2|a2⟩+ω−3|a3⟩+…+ω−r|1⟩) r
= √ω (ω−1|a⟩+ω−2|a2⟩+ω−3|a3⟩+…+|1⟩) r
In the third step, we use that ar = 1 (mod N), and in the fifth step, we use
ω−r = (e2πi/r)−r = e−2πi = (eπi)−2 = (−1)−2 = ((−1)2)−1 = 1−1 = 1
where the fourth step uses eπi = −1, which is Euler’s identity. Now we want to use Phase Estimation to get r.
Ideally, we run Phase Estimation on Ma and |ψ1⟩, which returns 1r , from which we can get r. However, we don’t have |ψ1⟩, so we do something else. Notice that
The fourth step uses the formula for a geometric sequence, and the fifth step uses our earlier calculation that ω−r = 1 so we get: (ω−l)r = (ω−r)l = 1l = 1.
So, instead of running Phase Estimation on Ma and |ψ1⟩, we run Phase Estimation on Ma and |1⟩. This is a lot like running Phase Estimation on Ma and |ψk⟩ for random choices of k, chosen uniformly. We will run Phase Estimation on Ma and |1⟩ many times. Each run produces kr ,
r−1 r−1 r−1 r−1 r−1 r−1 1∑∑−lkl 1∑∑−lkl 1∑∑−lk l
|ψk⟩=r ω |a⟩=r k=0 l=0
(ω)|a⟩=|1⟩+r (ω))|a⟩ l=1 k=0
l=0 k=0 1∑1−(ω−l)r l
= |1⟩+r l=1 1−ω−l |a⟩ = |1⟩+r l=1 1−ω−l|a⟩ = |1⟩

where we don’t know either of k and r. This is where the Continued Fraction Algorithm comes in. The Continued Fraction Algorithm plus some post-processing map a list of samples of kr to r (we skip the details). The Continued Fraction Algorithm runs in O((logN)3) time, which is a major contributor to the time complexity of Shor’s algorithm.
[Phase estimation uses the quantum Fourier transform as a subroutine]
The entire quantum part of Shor’s algorithm boils down to Phase Estimation. Turns out that Phase Estimation uses the Quantum Fourier Transform as a critical component. We skip the details of how this works.
[The quantum Fourier transform is exponentially faster than the classical FFT]
A milestone in Fourier analysis was the 1965 paper by Cooley and Tukey, which presented the Fast Fourier Transform (FFT) algorithm. The FFT algorithm computes the Discrete Fourier Transform in O(n log n) time. The FFT algorithm has become a cornerstone of many disciplines within Electrical Engineering and Computer Science. The FFT paper has been cited 15,640 times, according to Google Scholar.
The FFT paper is amazing and the O(nlogn) run time is blazingly fast, yet the quantum Fourier transform is exponentially faster. The quantum Fourier transform is due to Shor (1994).
Transition to Close: So there you have it.
Review: At the core of Shor’s algorithm is a subroutine for finding the order of an element in a group. This subroutine can be executed efficiently on a quantum computer. So, Shor’s algorithm is a hybrid algorithm that mixes classical computation and quantum computation. Notice the hierarchy of subroutines:
Integer Factorization
Shor’s Algorithm
Order Finding
1) Phase Estimation and 2) Continued Fractions Quantum Fourier Transform
which calls which calls which calls where (1) calls
Here, the quantum part of the algorithm lies in Phase Estimation and its use of the Quantum Fourier Transform.
Strong finish: Shor’s algorithm prompted cryptographers to study post-quantum cryptography and it created a lot of excitement about the promise of quantum computing.
Call to action: Find an implementation of Shor’s algorithm in Qiskit, or write it yourself, and run it on IBM’s quantum computer with input 21, and see if you get 3 × 7.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts