Hidden subgroup problems
Quantum computing can efficiently solve hidden subgroup problems (HSPs) for finite Abelian groups. Given a group , a subgroup , and a set , we say a function hides the subgroup if is constant on the cosets of , while it is different between the different cosets of . HSP is to determine a generating set of using as an oracle.
Simon's algorithm, quantum Fourier transformation, quantum phase estimation are all solutions to specific HSPs. We will demonstrate these algorithms using isQ examples.
Simon's algorithm
Given a function with the promise that, for some unknown , for all , where denotes bitwise XOR. The goal is to identify by making as few queries to as possible. Note that Furthermore, for some and in , is unique () if and only if . This means that is two-to-one when , and one-to-one when . It is also the case that implies , meaning that which shows how is periodic.
The quantum circuit used in Simon's algorithm is:
The measurement result of the first register satisfies Therefore, by executing the circuit times, we can get a list of independent bitstrings . With the help of a classical computer, we can calculate .
Next, we compose an example of Simon's algorithm in isQ. We choose and thus . Let (mod 8). Therefore, if and , differs from only by the highest bit, i.e., and (1000 as a bitstring). The complete code is as follows:
import std;
oracle bool[4] g(bool a[4]) {
bool res[] = {a[0], a[1], a[2], false};
return res;
}
procedure main(){
qbit q[4], res[4];
H(q);
g(q, res);
H(q);
print M(q);
}
We executed the program several times, and the first three outputs are 1, 3, and 6. It is easy to check that they are independent bitstrings. The only 4-bit bitstring that satisfies , , and is 8, precisely the secret bitstring we defined.
Quantum Fourier transformation
Quantum Fourier transform (QFT) is the quantum analogue of the discrete Fourier transform. It is a key component of many HSP solutions, such as Shor's algorithm.
QFT is a linear operator with the following action on the basis states: where and is the number of qubits. Equivalently, QFT can be given by the following product representation: where is the binary representation of , and represents the binary fraction .
Inspired by the product representation, we use the following quantum circuit to implement QFT: where Note that extra SWAP gates are needed at the end of the circuit to reverse the order of the qubits.
The isQ program describing the above circuit is:
import std;
procedure R(int k, qbit q) {
double phase = pi / 2 ** (k - 1);
ctrl GPhase(phase, q);
} deriving gate
procedure qft(qbit q[]) {
int len = q.length;
for i in len-1:-1:-1 {
H(q[i]);
for j in 0:i {
ctrl R(i-j+1, q[j], q[i]);
}
}
for i in 0:len/2 {
SWAP(q[i], q[len-i-1]);
}
}
// The inverse of qft
procedure qft_dagger(qbit q[]) {
int len = q.length;
for i in 0:len/2 {
SWAP(q[i], q[len-i-1]);
}
for i in 0:len {
for j in 0:i {
ctrl inv R(i-j+1, q[j], q[i]);
}
H(q[i]);
}
}
Note that ctrl
is a keyword that turns a gate into its controlled form, and its first qbit
argument is the control qubit. deriving gate
is a keyword that turns a procedure into a quantum gate. Measurement, branch, and loops cannot be used in such a procedure. .length
is another keyword that acquires the length of an array. The inverse of QFT, named qft_dagger
, is also defined here. It will be used in the following examples.
Quantum phase estimation
The quantum phase estimation (QPE) algorithm is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. More precisely, given a unitary matrix with an eigenvector , such that The algorithm estimates the value of with high probability.
The overall structure of the QPE algorithm is as follows:
First, gates are applied to to create the superposition of all numbers in . Then, the superposition controls the gate so that
After that, applying the inverse of QFT () to the first register results in a state similar to . For simplicity, we will not analyze the error.
The detailed circuit is shown as follows:
We choose whose eigenvector is and . The corresponding isQ program is as follows:
import std;
import qft; // include qft_dagger
int x = 23;
int n = 6;
double theta(){
return 2 * pi * x / (2 ** n);
}
procedure U(double theta, qbit q){
X(q);
ctrl GPhase(theta, q);
X(q);
} deriving gate
procedure pow2_ctrlU(int n, qbit anc, qbit ev){
double t = theta() * (2 ** n);
ctrl U(t, anc, ev);
}
int phase_estimation(int n, qbit ev) {
qbit anc[n];
for i in 0:n {
H(anc[i]);
pow2_ctrlU(i, anc[i], ev);
}
qft_dagger(anc);
return M(anc);
}
procedure main()
{
qbit ev;
ev = |0>; /* eigen vector of U */
print phase_estimation(n, ev);
}
Note that (qft_dagger
) is defined in qft.isq
and not shown here. After execution, the printed result is 23, the phase we set.
Shor's algorithm
Shor’s algorithm is one of the most well-known quantum algorithms and finds the prime factors for input integer in polynomial time. This algorithm could break public-key schemes since they are based on the assumptions that factoring large integers is computationally intractable.
To factor a composite number , Shor's algorithm is summarized below:
-
If is even, return the factor 2.
-
Determine whether for integers and , and if so return the factor .
-
Randomly choose in the range 1 to . If gcd then return the factor gcd.
-
Use the order-finding subroutine to find the order of modulo . The \textit{order} is the minimal positive integer so that .
-
If is even and then compute gcd and gcd, and test to see if one of these is a non-trivial factor, returning that factor if so. Otherwise, the algorithm fails.
Note that, in these steps, only Step 4 is conducted on a quantum machine. We will also focus on this part. The quantum circuit used for finding the order is
which is quite similar to the one used in QPE. The key reason that leads to this similarity is that the state defined by is an eigenvector of gate with the eigenvalue . Therefore, we can infer by estimating the phase.
When implementing the quantum part of Shor's algorithm, the most challenging part is implementing the modular exponentiation gate, which is detailed in the previous tutorial. Its cost is . Therefore, the cost of order finding and Shor's algorithm is also .
Next, we use isQ to demonstrate finding the factors of 15 following Shor's algorithm. In the order-finding step, we select and try to find its order using a quantum circuit.
// |0> -> |r> where 7 ^ r = 1 (mod 15)
int find_order(qbit k[6]) {
qbit a[4];
H(k);
X(a[0]); // set |a> = |1>
pow7mod15(k, a);
qft_dagger(k);
}
procedure main()
{
qbit k[6];
find_order(k);
bp; // check the amplitude of the state vector
print M(k);
}
After executing the program, four results can be printed with equal possibilities: 0, 16, 32, and 48. When the returned value is 16 or 48, we can get the fraction or . Thus, the order is 4, i.e., . Otherwise, we cannot infer the order, and the program needs to be executed again. Since gcd, we finally get 3 as a factor of 15.