© Vladimir Silva 2018
Vladimir SilvaPractical Quantum Computing for Developershttps://doi.org/10.1007/978-1-4842-4218-6_8

8. Faster Search plus Threatening the Foundation of Asymmetric Cryptography with Grover and Shor

Vladimir Silva1 
(1)
CARY, NC, USA
 
This chapter brings proceedings to a close with two algorithms that have generated excitement about the possibilities of practical quantum computation:

  • Grover’s search: This is an unstructured quantum search algorithm created by Lov Grover which is capable of finding an input with high probability using a black box function or Oracle. It can find an item in $$ Oleft(sqrt{N} ight) $$ steps as opposed to a classical average of N/2 steps.

  • Shor’s integer factorization: The notorious quantum factorization that experts say could bring current asymmetric cryptography to its knees. Shor can factorize integers in approximately log(n3) steps as opposed to the fastest classical algorithm, the Number Field Sieve at $$ exp left(kast log left({n}^{frac{1}{3}} ight)kern0.28em {left(log log kern0.28em n ight)}^{frac{2}{3}} ight) $$.

Let’s get started.

Quantum Unstructured Search

Grover’s algorithm is an unstructured search quantum procedure to find an entry of n bits on a digital haystack of N elements. As shown in Figure 8-1, Grover’s quantum algorithm provides significant speedup at $$ Oleft(sqrt{N} ight) $$ steps. It may not seem much compared to the classical solution, but when we are talking about millions of entries, then the square root of 106 is much faster than 106.
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig1_HTML.jpg
Figure 8-1

Unstructured search time complexities

If x is the element we are looking for, then Grover’s algorithm can be described by the following pseudocode:
  1. 1.

    Prepare the input given f: {0, 1, … , N-1} → {0,1}. Note that the size of the input is 2n where n is the number of bits and N is the number of steps or size of the haystack. The ultimate goal is to find x such that f(x) = 1.

     
  2. 2.

    Apply a basis superposition to all qubits in the input.

     
  3. 3.

    Perform a phase inversion on the input qubits.

     
  4. 4.

    Perform an inversion about the mean on the input.

     
  5. 5.

    Repeat steps 3 and 4 at least $$ sqrt{N} $$ times. There is a high probability that x will be found at this point.

     

Let’s take a closer look at the critical phase inversion and inversion about the mean steps.

Phase Inversion

This is the first step in the algorithm and must be performed in a superposition of all states in the haystack. If the element we are looking for is xʹ where f(xʹ) = 1, then the superposition can be expressed as ∑ α ∣ x⟩. Ultimately, what phase inversion does is
$$ sum alpha kern0.28em mid xleft angle {kern0.28em }^{underrightarrow{Phase Inversion}} ight{{displaystyle egin{array}{c}sum alpha kern0.28em mid xBig angle kern0.28em ifkern0.28em x e {x}^{prime}\ {}-alpha kern0.28em mid {x}^{prime}Big angle kern0.28em Otherwiseend{array}} $$
That is, if a given x is not the element we are looking for (x ≠xʹ), then it leaves the superposition intact; otherwise it inverts the phase (the sign of the complex coefficient α of the qubit – see Figure 8-2 for a pictorial representation).
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig2_HTML.jpg
Figure 8-2

Pictorial representation of phase inversion

This is the first step in Grover’s algorithm; we’ll see how phase inversion helps on finding the element we are looking for, but for now let’s look at the second step: inversion about the mean.

Inversion About the Mean

Given the previous superposition ∑ α ∣ x⟩, we define the mean μ, as the average value of the amplitudes:
$$ mu =frac{sum_{x=0}^{N-1}{propto}_x}{N} $$
Now we must flip the amplitudes about this mean. That is,
$$ {alpha}_x o left(kern0.28em 2mu -{alpha}_x ight) $$
$$ sum {alpha}_xkern0.28em mid xleft angle o sum left(kern0.28em 2mu -{alpha}_x ight)kern0.28em mid x ight angle $$
To better understand this, Figure 8-3 shows a pictorial representation of inversion about the mean.
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig3_HTML.jpg
Figure 8-3

Graphical representation of inversion about the mean

Figure 8-3 shows the superimposed state of the qubits as defined by the wave function ψ. The mean or μ of this function is shown as the horizontal line in the chart. What inversion about the mean does is it mirrors the wave function ψ over the mean μ resulting in a mirror wave (shown with a dotted line). This is equivalent to rotating the waves over the axis μ. Let’s make sense of all this by putting all steps together to see them in action:
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig4_HTML.jpg
Figure 8-4

Single Grover’s iteration

In Figure 8-4:

  • The superposition of all qubits puts all amplitudes at $$ frac{1}{sqrt{N}} $$.

  • Next, a phase inversion puts the amplitude for xʹ at $$ -frac{1}{sqrt{N}} $$. Note that this has the effect of lowering slightly the value of the mean μ, as shown by the dotted line in Figure 8-4 step 2.

  • After the inversion about the mean, the mean amplitude drops a little bit, but xʹ goes way high, as much as $$ frac{2}{sqrt{N}} $$ above the mean μ.

  • If we repeat this sequence, the amplitude of x’ increases by about $$ frac{2}{sqrt{N}} $$ until that, in about $$ sqrt{N} $$ steps, the amplitude becomes $$ frac{1}{sqrt{2}} $$.

  • At this point, if we measure our qubits, the probability of finding x’ (the element we are looking for), as defined by quantum mechanics, is the square of the amplitude. That is, ½.

  • Thus we are done. In roughly $$ sqrt{N} $$ steps, we have found the marked element xʹ.

Now, let’s put all this together in a quantum circuit and corresponding code implementation.

Practical Implementation

We’ll take a look at a circuit for Grover’s algorithm in IBM Q Experience. The circuit demonstrates a single iteration of the algorithm using 2 qubits as shown in Figure 8-5.
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig5_HTML.jpg
Figure 8-5

Quantum circuit for Grover’s algorithm with 2 qubits and A = 01

A Python script that creates the circuit in Figure 8-5 is shown in Listing 8-1.
import sys,time,math
# Importing QISKit
from qiskit import QuantumCircuit, QuantumProgram
# Q Experience config
sys.path.append('../Config/')
import Qconfig
# Import basic plotting tools
from qiskit.tools.visualization import plot_histogram
# Set the input bits to search for
def input_phase (circuit, qubits):
  # Uncomment for A = 00
  # Comment for A = 11
  circuit.s(qubits[0])
  #circuit.s(qubits[1])
  return
# circuit: Grover 2-qubit circuit
# qubits: Array of qubits (size 2)
def invert_over_the_mean (circuit, qubits):
  for i in range (2):
    circuit.h(qubits[i])
    circuit.x(qubits[i])
  circuit.h(qubits[1])
  circuit.cx(qubits[0], qubits[1])
  circuit.h(qubits[1])
  for i in range (2):
    circuit.x(qubits[i])
    circuit.h(qubits[i])
def invert_phase (circuit, qubits):
  # Oracle
  circuit.h(qubits[1])
  circuit.cx(qubits[0], qubits[1])
  circuit.h(qubits[1])
def main():
  # Quantum program setup
  qp = QuantumProgram()
  qp.set_api(Qconfig.APItoken, Qconfig.config["url"])
  # Create qubits/registers
  size = 2
  q = qp.create_quantum_register('q', size)
  c = qp.create_classical_register('c', size)
  # Quantum circuit
  grover = qp.create_circuit('grover', [q], [c])
  # 1. put all qubits in superposition
  for i in range (size):
    grover.h(q[i])
  # Set the input
  input_phase(grover, q)
  # 2. Phase inversion
  invert_phase(grover, q)
  input_phase(grover, q)
  # 3. Invert over the mean
  invert_over_the_mean (grover, q)
  # measure
  for i in range (size):
    grover.measure(q[i], c[i])
  circuits = ['grover']
  # Execute the quantum circuits on the simulator
  backend = "local_qasm_simulator"
  # the number of shots in the experiment
  shots = 1024
  result = qp.execute(circuits, backend=backend, shots=shots
           , max_credits=3, timeout=240)
  counts = result.get_counts("grover")
  print("Counts:" + str(counts))
  # Optional
  #plot_histogram(counts)
###########################################
# main
if __name__ ==  '__main__':
  start_time = time.time()
  main()
  print("--- %s seconds ---" % (time.time() - start_time))
Listing 8-1

Python Script for Circuit in Figure 8-5

  • Listing 8-1 performs a single interaction of Grover’s algorithm for a 2-bit input using 2 qubits. Even though the pseudocode in the previous section states that the total number of iterations is given by roughly $$ sqrt{N} $$ steps, the inversion about the mean requires this value to be multiplied by π/4 and its floor extracted (see the proof next to Figure 8-8). Therefore, we end up with $$ IT= floorleft(sqrt{N}ast frac{pi }{4} ight) $$ where N = 2bits. Thus, for 2 bits we get $$ IT= floorleft(sqrt{4}ast frac{pi }{4} ight)= floor(1.57)=1 $$.

  • The script begins by creating a quantum circuit with 2 qubits and two classical registers to store their measurements.

  • Next, all qubits are put in superposition using the Hadamard gate.

  • Before the iteration, the input is prepared using the phase gate (S) and the rules in Table 8-1.
    Table 8-1

    Input Preparation Rules for Listing 8-1

    Input (A)

    Gates/qubits

    00

    S(01)

    10

    S(0)

    01

    S(1)

    11

    None

  • Next, perform a phase inversion followed by an inversion about the mean on the input qubits corresponding to a single iteration of the algorithm.

  • Finally, measure the results and execute the circuit in the local or remote simulator. Print the result counts.

Generalized Circuit

In broad terms, the circuit in Figure 8-5 can be generalized to any number of input qubits as shown in Figure 8-6.
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig6_HTML.jpg
Figure 8-6

Generalization of Grover’s algorithm for an arbitrary number of qubits

  • The first box in Figure 8-6 puts all qubits in superposition by applying the Hadamard gate to the input of size n. This is the initialization step.

  • Next, the phase inversion circuit (Uf) receives the superimposed input ψ =  ∑ α ∣ x⟩ and a phase input (minus state). This has the desired effect of putting the phase exactly where we want it. Thus the output becomes ∑ α (−1)f(x) ∣ x⟩. But how can this be achieved? The answer is that, by applying an exclusive OR on the minus state input, we obtain the desired effect ∣b⟩ →  ∣ f(x) ⊕ b⟩ as shown in Figure 8-7. The third row of the XOR truth table between f(x) and b (the right side of Figure 8-7) shows the phase inversion effect.
    ../images/469026_1_En_8_Chapter/469026_1_En_8_Fig7_HTML.jpg
    Figure 8-7

    Phase inversion circuit

  • Finally, as shown in Figure 8-3, inversion about the mean is the same as doing the reflection about $$ mid mu left angle =1/sqrt{N}sum limits_xmid x ight angle $$. To better visualize this, the superimposed state ψ and the mean μ can be represented as vectors over a 2D space as shown in Figure 8-8. To reflect ψ, create an orthogonal vector to μ, then project ψ over the new quadrant at the same angle θ.

../images/469026_1_En_8_Chapter/469026_1_En_8_Fig8_HTML.jpg
Figure 8-8

Inversion over the mean circuit

The proof that inversion over the mean transforms ∑ αx ∣ x⟩ →  ∑ (2μ − αx) ∣ x⟩ involves three steps, as shown by the circuit in Figure 8-8.
  1. 1.

    Transform |μ> to the all zeros vector ∣0, …, 0⟩. This is achieved by applying the Hadamard gate to the input.

     
  2. 2.

    Reflect about the all zeros vector ∣0, …, 0⟩. This can be done by multiplying it by the sparse matrix $$ left[egin{array}{cccc}1& cdots & cdots & 0\ {}0& -1& & vdots \ {}vdots & cdots & ddots & vdots \ {}0& cdots & & -1end{array} ight] $$

     
  3. 3.

    Transform ∣0, …, 0⟩ back to |μ> by applying the Hadamard again. Thus

     
$$ {H}^{otimes n}kern0.28em left[egin{array}{cccc}1& cdots & cdots & 0\ {}0& -1& & vdots \ {}vdots & cdots & ddots & vdots \ {}0& cdots & & -1end{array} ight]kern0.28em {H}^{otimes n}={H}^{otimes n}kern0.28em left(left[egin{array}{ccc}2& cdots & 0\ {}vdots & ddots & vdots \ {}0& cdots & 0end{array} ight]-I ight){H}^{otimes n}={H}^{otimes n}kern0.28em left[egin{array}{ccc}2& cdots & 0\ {}vdots & ddots & vdots \ {}0& cdots & 0end{array} ight]{H}^{otimes n}-{H}^{otimes n}Ikern0.28em {H}^{otimes n} $$
                                    
$$ =kern0.5em left[egin{array}{ccc}2/N& cdots & 2/N\ {}vdots & ddots & vdots \ {}2/N& cdots & 2/Nend{array} ight]-I=left[egin{array}{ccc}frac{2}{N}-1& cdots & 2/N\ {}vdots & ddots & vdots \ {}2/N& cdots & frac{2}{N}-1end{array} ight] $$
(1)
Note that $$ {H}^{otimes n}Ikern0.28em {H}^{otimes n}=Ikern0.28em andkern0.5em H=frac{2}{sqrt{N}}mid xBig angle $$. Finally, applying matrix (1) to the state ψ = αx ∣ x⟩ yields
$$ left[egin{array}{ccc}frac{2}{N}-1& cdots & 2/N\ {}vdots & ddots & vdots \ {}2/N& cdots & frac{2}{N}-1end{array} ight]left[egin{array}{c}{alpha}_0\ {}vdots \ {}{alpha}_x\ {}vdots \ {}{alpha}_{N-1}end{array} ight] o left[egin{array}{c}\ {}vdots \ {}2/Nsum {alpha}_y-{alpha}_x\ {}vdots \ {}end{array} ight]=2mu -{alpha}_xkern0.28em wherekern0.28em 2/Nsum {alpha}_y=2mu $$

So this is Grover’s algorithm for unstructured search. It is fast, powerful, and soon to be hard at work on the data center cranking up all kinds of database searches. Given its significant performance boost over its classical cousin, chances are that in a few years, when quantum computers become more business friendly, most web searches will be performed by this quantum powerhouse. Before we finish, it is worth noting that, by the time of this writing, a useful implementation or experiment (one that can find a real thing) does not exist for IBM Q Experience. Hopefully this will change in the future, but for now Grover’s algorithm lives in the theoretical side of things. In the next section, we close strong by looking at the famous Shor’s algorithm for integer factorization.

Integer Factorization with Shor’s Algorithm

The game of cat and mouse between cryptography and crypto analysis rages on: the first, devising new ways to encrypt our everyday data, and the latter probing for weaknesses, always looking for a crack to bring it down. Current asymmetric cryptography relies on the well-known difficulty of factoring very large primes (in the hundreds of digits range). This section looks at the inner workings of Shor’s algorithm, a method that gives exponential speedup for integer factorization using a quantum computer. This is followed by an implementation using a library called ProjectQ. Next, we simulate for sample integers and evaluate the results. Finally we look at current and future directions of integer factorization in quantum systems. Let’s get started.

Challenging Asymmetric Cryptography with Quantum Factorization

In the pivotal paper “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,”1 Peter Shor proposed a quantum factorization method using a principle known to mathematicians for a long time: find the period (also known as order) of an element a in the multiplicative group modulo N, that is, the least positive integer such that
$$ {x}^requiv 1kern0.28em left(operatorname{mod}kern0.28em N ight) $$

where N is the number to factor and r is the period of x modulo N.

Tip

Large integer factorization is a problem that has puzzled mathematicians for millennia. In 1976, G. L. Miller postulated that using randomization, factorization can be reduced to finding the period of an element a modulo N, thus greatly simplifying this puzzle. This is the basic idea behind Shor’s algorithm.

Shor divided his algorithm in three stages, two of which are performed by a classical computer in polynomial time:
  1. 1.

    Input preparation: Done in a classical computer in polynomial time log (n).

     
  2. 2.

    Find the period r of the element a such that ar ≡ 1 (mod N) via a quantum circuit. According to Shor, this takes O((log n)2(log log n)(log log log n)) steps on a quantum computer.

     
  3. 3.

    Postprocessing: Done in a classical computer in polynomial time log (n).

     
But why is there so much excitement about this method? Compare its time complexity (big O) against the current classical champ: the Number Field Sieve as shown in Table 8-2 (including another fan favorite, the venerable Quadratic Sieve).
Table 8-2

Time Complexities for Common Factorization Algorithms

Algorithm

Time complexity

Shor’s

(logn)2(log log n) (log log  log n)

Number Field Sieve

$$ exp left(ckern0.28em {left(log n ight)}^{1/3}{left(log log n ight)}^{frac{2}{3}} ight) $$

Quadratic Sieve

$$ exp left(sqrt{ln nln ln n} ight) $$

Incredibly, Shor’s algorithm has a polynomial time complexity, far superior to the exponential time by the Number Field Sieve, the fastest known method for factorization in a classical computer. As a matter of fact, experts have estimated that Shor’s could factor a 200+ digit integer in a matter of minutes. Such a feat would rock the foundation of current asymmetric cryptography used to generate the encryption keys for all of our web communications.

Tip

Symmetric cryptography is highly resistant to quantum computation and thus to Shor’s algorithm.

But don’t panic yet; a practical implementation in a real quantum computer is still a long way. Nevertheless, the algorithm can be simulated in a classical system using the slick Python library: ProjectQ. We’ll run ProjectQ’s implementation in a further section, but next let’s see how period finding can solve the factorization problem efficiently.

Period Finding

Period finding is the basic building block of Shor’s algorithm. By using modular arithmetic, the problem is reduced to finding the period (r) of the function f(x) = ax mod N (see Figure 8-9).
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig9_HTML.jpg
Figure 8-9

Periodic function f(x)

Figure 8-9 gives an example of a periodic function f(x) with period r = 4. For the algorithm to work, f(x) must meet three conditions:
  1. 1.

    f(x) is one-to-one on each period; that is, the values of f(x) must not repeat. In Figure 8-9 these values are represented by the vertices of each line per period.

     
  2. 2.

    For any given M or the number of periods, r must divide M. For example, given M = 100 and the period r = 4, M/r = 25.

     
  3. 3.

    M divided by r must be greater than r. That is, M > r2.

     

Shor’s algorithm transforms f(x) into a quantum circuit Uf where the inputs are in superposition. If we measure the second register in Uf, we may see values for the amplitudes $$ sum limits_{x=0}^{M-1}{propto}_xmid xBig angle $$ as shown in the amplitude chart of Figure 8-9. Here the amplitudes are exactly four units apart which is the period we are looking for. In this particular case, we get periodic superpositions with r = 4. But what do we do with this periodic superposition? Shor’s relies on another trick: Fourier sampling or quantum Fourier transform.

Fourier Sampling

Fourier sampling is a data manipulation process that has the following properties:

  • It allows for input shifting without changing the output distribution.

  • This is good because now we have a periodic superposition where the non-zero amplitudes are the multiples of the period (see Figure 8-10).

../images/469026_1_En_8_Chapter/469026_1_En_8_Fig10_HTML.jpg
Figure 8-10

Fourier sampling showing periodic superposition

But what is the output of Fourier sampling? And how does it help? The answer is that its output is a random multiple of M/r. In this case given M = 100 and r = 4, we get a random multiple of 100/4 = 25. This is advantageous for our goal. Let’s see how.

Feed the Fourier Sampling Results to Euclid’s Greatest Common Divisor

If we were to run Fourier sampling multiple times, we will get random multiples of M/r. For example, we may get 50, 75, 25, etc. Now, if we apply Euclid’s greatest common divisor (gcd) to our random outputs, then viola: By dividing M by the gcd, we get the period r. Thus

r = M/gcd(50, 75, …) = 100 /25 = 4

So this is the outline for period finding via a quantum circuit. To understand how this method can find a factor efficiently, let’s run through an example by factoring the number N = 21. Our task relies on two very efficient operations:

  • Modular arithmetic: a = b (mod N). For example, 3 = 15 (mod 12).

  • Greatest common divisor gcd(a, b). For example, gcd(15, 21) = 3.

Thus for N = 21, we need to solve the equation x2 ≡ 1 (mod 21). That is, find the nontrivial square root x such that

  • N divides (x +1) (x – 1).

  • N does not divide (x ± 1).

  • Finally, recover a prime factor by applying gcd(N, x+1).

To find the nontrivial factor for N = 21, pick a random x. For example, given N = 21, choose x = 2; thus
20 ≡ 1 (mod 21)
21 ≡ 2 (mod 21)
22 ≡ 4 (mod 21)
23 ≡ 8 (mod 21)
24 ≡ 16 (mod 21)
25 ≡ 11 (mod 21)
26 ≡ 1 (mod 21). Got the period r = 6.

In this case, 26 = (23)2. Thus 23 = 8 is a nontrivial factor such that 21 divides (8 + 1)(8 – 1). Finally we recover a factor with the greatest common divisor gcd (N, x+1) = gcd(21, 9) = 3. In general terms, pick an x at random, and then loop through x0, x1,…, xr ≡ mod N. If we are lucky, then r is even, that is, (xr/2)2 ≡ 1 (mod N). And thus we have a nontrivial square root of 1 mod N.

Tip

It has been proven that the probability that we get lucky, that is, r is even for x2 ≡ 1 (mod N), is ½. If we are unlucky, on the other hand, then we must repeat the procedure all over again. However given the high probability of success, this would be insignificant in the great scheme of things.

Now, let’s run the algorithm using the slick Python library ProjectQ.

Shor’s Algorithm by ProjectQ

ProjectQ is an open source platform for quantum computing that implements Shor’s algorithm using the circuit proposed by Stéphane Beauregard2. This circuit uses 2n + 3 qubits where n is the number of bits of the number N to factor. Beauregard’s method is divided into the following steps:
  1. 1.

    If N is even, return the factor 2.

     
  2. 2.

    Classically determine if N = pq for p ≥ 1 and q ≥ 2, and if so, return the factor p (in a classical computer, this can be done in polynomial time).

     
  3. 3.

    Choose a random number a, such that 1 < a ≤ N – 1. Using Euclid’s greatest common divisor, determine if gcd (a, N) > 1. If so, return the factor gcd(a, N).

     
  4. 4.

    Use the order-finding quantum circuit to find the order r of a modulo N. In a quantum computer, this step is done in polynomial time.

     
  5. 5.

    If r is odd or r is even but ar/2 = –1 (mod N), then go to step 3. Otherwise compute gcd(ar/2 – 1, N) and gcd(ar/2 + 1, N). Test to see if one of these is a nontrivial factor of N, and return the factor if so (in a classical computer, this can be done in polynomial time).

     
../images/469026_1_En_8_Chapter/469026_1_En_8_Fig11_HTML.jpg
Figure 8-11

Beauregard quantum circuit for period finding

Beauregard implements period finding by using a series of controlled additions and multiplications in Fourier space to solve f(x) = ax(mod N) → ar ≡ 1 mod N (see Figure 8-11):
  • A controlled multiplier Ua maps ∣x⟩ →  ∣ ax (mod N)⟩ where

    • a is a classical relative prime to use as the base for ax (mod N).

    • x is the quantum register.

    • c is the register of control qubits such that Ua = ax (mod N) if c =1 and x otherwise.

  • The controller multiplier Ua is in turn implemented as a series of doubly controlled modular adder gates such that

    • If both control qubits c1 = c2 = 1, the output is f(x) =  ∣ φ(a+b mod N)⟩. That is, a + b (mod N) in Fourier space. Note that this gate adds two numbers: a relative prime (a) and a quantum number (b).

    • If either control qubit (c1, c2) is in state |0>, then f(x) =  ∣ φ(b )⟩.

  • The doubly controlled modular adder gate is in turn built on top of the quantum addition circuit by Draper3. This circuit implements addition of a classical value (a) to the quantum value (b) in Fourier space.

Factorization with ProjectQ

Let’s install ProjectQ and put the algorithm to the test. The first thing to do is to use the Python package manager to download and install ProjectQ (note that I am using Windows for the sake of simplicity. Linux users should be able to follow the same procedure):
C:> pip install projectq
Next, grab the shor.py script from ProjectQ’s examples folder4 or the book source under WorkspaceCh08p08-shor.py. Now, run the script and enter a number to factor (see Listing 8-2).
C:>python shor.py
Number to factor: 21
Factoring N = 21: ..........
Factors found : 7 * 3 = 21
Gate class counts:
    AllocateQubitGate : 166
    CCR : 1467
    CR : 7180
    CSwapGate : 50
    CXGate : 200
    DeallocateQubitGate : 166
    HGate : 2600
    MeasureGate : 11
    R : 608
    XGate : 206
Gate counts:
    Allocate : 166
    CCR(0.098174770425) : 18
    CCR(0.196349540849) : 30
    CCR(0.392699081699) : 70
    CCR(0.490873852124) : 18
    CCR(0.785398163397) : 80
    CCR(0.981747704246) : 38
    CCR(1.079922474671) : 20
    CCR(1.178097245096) : 16
      ...
    R(5.252350217719) : 1
    R(5.301437602932) : 1
    R(5.497787143782) : 1
    X : 206
Max. width (number of qubits) : 13.
--- 5.834410190582275 seconds ---
Listing 8-2

Shor’s Algorithm by ProjectQ in Action

For N = 21, the script dumps a set of very helpful statistics such as

  • The number of qubits used: Given N = 21 we need 5 bits; thus total-qubits = 2 * 5 + 3 = 13.

  • The total number of gates used by type: In this case, doubly controlled CCR = 1467, CR = 7180, CSwap = 50, CX = 200, R = 608, X = 206, and others, for a grand total of 12,646 quantum gates.

ProjectQ implements quantum period finding using Beauregard algorithm as shown in Listing 8-3:
  • The run_shor function takes three arguments:

    • The quantum engine or simulator provided by ProjectQ plus

    • N: The number to factor

    • a: The relative prime to use as a base for ax mod N

  • The function then loops from a = 0 to a = ln(N) with the quantum input register x in superposition; it then performs the quantum circuit for f(a) = ax mod N as shown in Figure 8-11.

  • Next, it performs Fourier sampling on the x register conditioned on previous outcomes and performs measurements.

  • Finally it sums the measured values into a number in range [0,1]. It then uses continued fraction expansion to return the denominator or potential period (r).

def run_shor(eng, N, a):
  n = int(math.ceil(math.log(N, 2)))
  x = eng.allocate_qureg(n)
  X | x[0]
  measurements = [0] * (2 * n)  # will hold the 2n measurement results
  ctrl_qubit = eng.allocate_qubit()
  for k in range(2 * n):
    current_a = pow(a, 1 << (2 * n - 1 - k), N)
      # one iteration of 1-qubit QPE
    H | ctrl_qubit
    with Control(eng, ctrl_qubit):
      MultiplyByConstantModN(current_a, N) | x
    # perform inverse QFT --> Rotations conditioned on previous outcomes
    for i in range(k):
      if measurements[i]:
        R(-math.pi/(1 << (k - i))) | ctrl_qubit
    H | ctrl_qubit
    # and measure
    Measure | ctrl_qubit
    eng.flush()
    measurements[k] = int(ctrl_qubit)
    if measurements[k]:
      X | ctrl_qubit
  Measure | x
  # turn the measured values into a number in [0,1)
  y = sum([(measurements[2 * n - 1 - i]*1. / (1 << (i + 1)))
       for i in range(2 * n)])
  # continued fraction expansion to get denominator (the period?)
  r = Fraction(y).limit_denominator(N-1).denominator
  # return the (potential) period
  return r
Listing 8-3

ProjectQ Period Finding Quantum Subroutine

The next section compiles a set of factorization results for various values of N.

Simulation Results

ProjectQ’s period finding subroutine is a simulation of a quantum circuit on a classical computer so it is not practical to use it to factorize large numbers. As a matter of fact, it is not capable to factor numbers larger than four digits in reasonable time on a home PC. Table 8-3 shows a set of results for various values of N gathered from my laptop up to 2491.
Table 8-3

Factorization Results for Various Values of N

Number (N)

Qubits

Time (s)

Memory (MB)

Quantum gate counts

15

11

2.44

50

CCR = 792

CR = 3186

CSwap = 32

CX = 128

H = 1408

R = 320

X = 130

Measure = 9

105

17

27.74

200

CCR = 3735

CR = 25062

CSwap = 98

CX = 392

H = 6666

R = 1568

X = 393

Measure = 15

1150

25

17542.12 (4.8 h)

500

CCR = 15366

CR = 139382

CSwap = 242

CX = 968

H = 24222

R = 5829

X = 981

Measure = 23

2491

27

246164.74 (68.3 h)

2048

CCR = 20601

CR = 194670

CSwap = 288

CX = 1152

H = 31126

R = 7509

X = 1166

Measure = 25

Factorizing the four-digit number 2491 took more than 68 hours on a 64-bit Windows 7 PC with an Intel Core i-5 CPU at 2.6 GHz with 16 GB of RAM. I tried to go a bit higher by attempting to factorize N = 8122 but gave up after one week. All in all, these results show that the algorithm can be simulated successfully for small numbers of N; however it needs to be implemented in a real quantum computer to test its real power.

This chapter brought proceedings to a close with two algorithms that have generated excitement about the possibilities of practical quantum computation: Grover’s algorithm, an unstructured quantum search method capable of finding inputs at an average of square root of N steps. This is much faster than the best classical solution at an average of N/2 steps. Expect all web searches to be performed by Grover’s algorithm in the future.

Shor’s algorithm for factorization in a quantum computer which experts say could bring current asymmetric cryptography to its knees. Shor’s, arguably the most famous quantum algorithm out there, is a prime example of the power of quantum computation by providing exponential speedups over the best classical solution.

Finally, I would like to close things up by saying that I have tried my best to explain the difficult concepts of quantum computing by mixing math, software, and as many figures I can muster. A lot of coffee cups and sleepless nights were spent writing this manuscript, not to mention that I find most of the math as confusing as you probably do. I hope you enjoy reading this book as much as I did writing it, and remember: The great physicist Richard Feynman once said “If somebody tells you that he understands Quantum Mechanics it means he doesn’t understand Quantum Mechanics.”

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.15.154.69