Quantum Period Finding(QPF)
How to find period of a function using QFT?
In the previous article, we have discussed about Quantum Phase Estimation (QPE).
In this article, we discuss about the Quantum Period Finding algorithm for a given Integer N by using the Quantum phase estimation, Quantum Fourier Transform, Continued Fractions Algorithm and Greatest Common Divisor Algorithm.
We implement the quantum period finding algorithm using qiskit for N =21 and Cirq for N =15.
setup:
Period-finding algorithm seeks to find the period, r, of a periodic function f(x) whose domain is a finite set of integers as shown below,
Typically N can be very large; we can even consider the domain to be all of Z, although the above mentioned case will be shown to be an equivalent finitization that makes the problem tractable.
First, for this to even make sense r has to be less than N so that such periodicity is “visible” by looking at the N domain points available to us.
Second, this kind of periodicity is more “traditional” than Simon’s, since here we use ordinary addition to describe the period r via f(x) = f(x + r) rather than the mod-2 periodicity of Simon, in which f(x) = f(x ⊕ r).
Modular Arithmetic:
we are interested in remainder when divide A by B, we can use an operator called modular operator.
An example, as shown below
Greatest Common Divisor:
Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B.
The Euclidean Algorithm for finding GCD(A,B) is as follows:
- If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
- If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
Write A in quotient remainder form as A = B * Q + R
Here R is A mod B, then find GCD(B,R) or GCD(B, A mod B). since GCD(A,B) = GCD(B,R) until we reach to any one of the steps mentioned above.
example:
GCD of 270, 192 is ?
GCD of 192, 78 is ?
GCD of 78, 36 is ?
GCD of 36, 6 is ?
GCD of 6, 0 is ?
Finally,
Period Finding:
Let’s take an example with power’s of 2:
below is the graph for mod 21 result set,
mod 21 values are formulated in a table as shown below, where right side table is after rearranging the output columns
classical solution:
classical order finding function returns period of the function
randomly generates the value of a
when we perform measurement on the rearranged data as shown in the above tabular form we could observe any of the sets,
in case of set with 1
|0⟩ + |6⟩ + |12⟩ + |18⟩ + |24⟩ + …
in case of set with 11
|5⟩ + |11⟩ + |17⟩ + |23⟩ + |29⟩ + …
If we have 9 qubits: there are 2⁹ = 512 basis states, which means 0 through 511, and we are creating interference across them.
Since we have divided them up in to 6 equal sets, there are about 512/6≈85 members on each set. This number shows up in the QFT of superposition.
Once we have the result, we then take that and turn it into the period. If we measure and find, for example, the value 85, then we use the value 512/85≈6 (period).
we will capture the data as shown in graph and tables above by using quantum computing with Quantum phase estimation and Quantum Fourier Transform.
Quantum Period Finding:
Problem:
Let, f : {0, 1, 2, . . . , N-1} → {0, 1, 2, . . . , N-1} be a periodic function of period r, meaning that
and the values f(x), f(x + 1), f(x + 2), . . . , f(x + r − 1) are all distinct.
from modulo, modular arithmetic and period finding explanation as discussed above our periodic function can be written as shown below,
where a is some number less than N and which has no factors in common with N. The period is the smallest value x = r such that
Let’s discuss about how this modular exponentiation we are going to achieve.
Modular Exponentiation:
how to evaluate the below expression
let’s consider B = 2 then the expression can be written as shown follow
example:
for B > 2 let’s consider B = 117 then the expression can be written as shown below
example:
let’s write 117 as shown below
by using the above form we can write as shown below
from fast modular exponentiation, we write the following
finally, after substituting the above results as shown below
from the above discussion on modular exponentiation we can observe that if we have a Unitary operator which performs step by step mod N operation we can arrive to the condition as shown below
this we can achieve by phase estimation algorithm because x is in the power of a, which means we need a control unitary operations as U¹, U², U⁴, U⁸ … where the powers are 2⁰, 2¹, 2², 2³…
Algorithm:
where |x, y⟩ goes to |x, y ⊕ f(x)⟩, Uf is again its own inverse.
Here if we set |y⟩ = |0⟩ then |y ⊕ f(x)⟩ becomes |f(x)⟩ which gives us easy way to evaluate f(x). so the input to the second register shall be |0⟩ for n times with out applying superposition.
With the above considerations the circuit becomes as shown in below
From above fig, we see a familiar pattern. There are two multi-dimensional registers, the upper (which we consider as A register or the data register), and the lower (which we consider as B register or the target register).
Analysis:
We discuss the behavior of the waveform at the particular intervals as shown in the above fig
How many qubits shall be consider for the data register and target register?
N² ≤ M ≤ 2N²
Here we use N for target register and 2N² for data register.
sending 2n-qubit |0⟩ or m -qubit |0⟩ to data register and n-qubit |0⟩ to target register as shown in the above fig and the |ψ0⟩ is represented as shown below.
We can see the output state of this Hadamard operator as the (2n)th order x-basis. It reminds us that not only do Hadamard gates provide quantum parallelism but double as a Z ↔ X basis conversion operator.
After the setting |y⟩ = |0⟩ and sending the inputs through the Oracle Uf which becomes |y ⊕ f(x)⟩ to |f(x)⟩ as shown below.
by writing x in-terms of binary(here let’s consider 2n as m for the following simplification), that is
by using this description of x, we can write the function as,
by expanding and rewriting of f we get,
we convert this formula to an inductive definition of f we shall define
Notice that
In other words, whether or not we should multiply
It turns out that as long as a and N are co-prime, the operation of multiplying
So for each j, there is a unitary operator.
which tells us, we can implement our f using phase estimation with change of |1⟩ in the second register or the most significant qubit shall be |1⟩ in case if the second register contains more than one qubit as we discussed above.
by considering
and also
Conceptually after performing the measurement at the register B or register-2 or target register for |ψ2⟩ and substituting the |f(x)⟩ and QFT|q/r⟩ from above, we get |ψ3⟩ as shown below
After applying the Inverse Quantum Fourier Transform on |ψ3⟩, we get |ψ4⟩ as shown below
After performing measurement on the register-A or register-1 we get the result similar to what we have discussed in the quantum phase estimation (QPE).
By applying the continued fraction algorithm on the first register which is Data register gives us the value of r or period of the function.
for phase = 0.5 and N = 21 the values of q and r be 1 and 2
we can verify that q/r = 1/2 = 0.5 which is phase.
Implement Quantum Period finding using qiskit and Cirq:
In this section we implement Quantum Period Finding(QPF) circuit using qiskit for N = 21 which have factors as 1, 3, 7, 21 and using cirq for N = 15 which have factors as 1, 3, 5, 15.
Implement QPF using qiskit:
As shown in the below qiskit1, generates initial conditions for the QPE algorithm
As shown in the below qiskit2, prepares a^x mod N for the QPF algorithm.
As shown in the below qiskit3, generates Controlled U circuit for the given function.
As shown in the below qiskit4, prepares psi wave function for the QPF algorithm.
As shown in the below qiskit5, generates Inverse Quantum Fourier Transform.
As shown in the below qiskit6, generates Quantum Period Finding circuit for the given function.
As shown in the below qiskit7, generates value of a for the given function.
As shown in the below qiskit8, initializes the circuit, number of qubits, generates the QPF circuit.
visualize the generated circuit for the given function as shown in below qiskit9.
As shown in the below qiskit10, performs measurement using simulator.
After the circuit running over simulator, capture the period of the function using continued fractions algorithm as shown below period is 2
Implement QPF using cirq:
the below function generates initial conditions for the QPF algorithm
the below function generates Controlled Unitary circuit for the given function.
the below function prepares psi wave function for the QPF algorithm.
the below function generates Inverse Quantum Fourier Transform.
the below function generates the Quantum period finding circuit using quantum phase estimation.
the below function captures the period of the given result using continued fractions algorithm as shown below
the below function performs the measurement of the circuit and returns the period of the function
the below function generates value of a for the given function.
the below block initializes the qubits and captures the period of the function
references: qiskit textbook, cirq tutorials, IITM course by (@Prabha M, Anil Prabhakar, @Valliamai Ramanathan, and @chandrashekar radhakrishnan), Qubit by Qubit(The Coding School) course, IBM Quantum Challenge 2021, QWorld (QSilver 2021), Textbook by Isaac Chuang and Michael Nielsen, Wikipedia, stack exchange and open source materials.
