import matplotlib.pyplot as plt
import numpy as np
from typing import *
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector, Operator
from qiskit_aer import AerSimulator
sim = AerSimulator()
from util import zero, one, qft
Shor’s Part 3/5: Modular Exponentiation#
References
Introduction to Classical and Quantum Computing, Chapter 7.9.3
Introduction to Quantum Information Science: Lecture 19 by Scott Aaronson
Quantum Computation and Quantum Information: Chapter 5, Nielsen and Chuang
Quantum Oracle for Modular Multiplication#
Suppose we have a unitary
so that
Question: why don’t we need an xor oracle?
Example#
Consider
where
a = 7; N = 15
xs = [x for x in range(N)]
ys = [(a ** x) % N for x in xs]
plt.plot(xs, ys, marker='x'); plt.title("a=7 and N=15")
Text(0.5, 1.0, 'a=7 and N=15')
Quantum Oracle#
Let
be the binary expansion of in 4 bits where is the most significant bit.Our goal is to construct the unitary
where
def amod15(a, power):
# Adapted From: https://qiskit.org/textbook/ch-algorithms/shor.html
if a not in [2,4,7,8,11,13]:
raise ValueError("'a' must be 2,4,7,8,11 or 13")
U = QuantumCircuit(4)
for iteration in range(power):
if a in [2,13]:
U.swap(2,3); U.swap(1,2); U.swap(0,1)
if a in [7,8]:
U.swap(0,1); U.swap(1,2); U.swap(2,3)
if a in [4, 11]:
U.swap(1,3); U.swap(0,2)
if a in [7,11,13]:
for q in range(4):
U.x(q)
U = U.to_gate(); U.name = "%i^%i mod 15" % (a, power);
return U
qc_amod15 = QuantumCircuit(4)
qc_amod15.append(amod15(7, 2**0), [0, 1, 2, 3])
U_f = Operator(qc_amod15)
qc_amod15.draw(output="mpl", style="iqp")
print((1 * 7) % 15) # Check that we get binary 7 (little endian)
(zero ^ zero ^ zero ^ one).evolve(U_f).draw("latex")
7
print((3 * 7) % 15) # Check that we get binary 6 (little endian)
(zero ^ zero ^ one ^ one).evolve(U_f).draw("latex")
6
Iterating Applications of #
Observe that if we iteratively apply
to itself
Thus we can encode the original function as
so that we can sequence
# Starting vector (reminder: little endian)
(zero ^ zero ^ zero ^ one).draw("latex")
# U_f |0001> (reminder: little endian)
(zero ^ zero ^ zero ^ one).evolve(U_f).draw("latex")
U_f2 = U_f.compose(U_f)
# U_f^2 |0001> (reminder: little endian)
(zero ^ zero ^ zero ^ one).evolve(U_f2).draw("latex")
U_f3 = U_f.compose(U_f2)
# U_f^3 |0001> (reminder: little endian)
(zero ^ zero ^ zero ^ one).evolve(U_f3).draw("latex")
U_f4 = U_f.compose(U_f3)
# U_f^4 |0011> = |0001> (reminder: little endian)
# Recall that the order was 4
(zero ^ zero ^ zero ^ one).evolve(U_f4).draw("latex")
Aside: Eigenvectors and Eigenvalues#
We say that
Eigenvectors and eigenvalues of #
is an eigenvector of with eigenvalue .Are there other eigenvectors/eigenvalues of
?Let
be an equal superposition of the powers of
(1/2.*((zero ^ zero ^ zero ^ one).evolve(U_f) +
(zero ^ zero ^ zero ^ one).evolve(U_f2) +
(zero ^ zero ^ zero ^ one).evolve(U_f3) +
(zero ^ zero ^ zero ^ one))).draw("latex")
# Checking eigenvector
(1/2.*((zero ^ zero ^ zero ^ one).evolve(U_f) +
(zero ^ zero ^ zero ^ one).evolve(U_f2) +
(zero ^ zero ^ zero ^ one).evolve(U_f3) +
(zero ^ zero ^ zero ^ one))).evolve(U_f).draw("latex")
More useful eigenvectors and eigenvalues of ?#
It is a fact that unitary matrices have unit norm eigenvalues.
Consequently, we might wonder if it possible to have phases
as eigenvalues.Where might we get such eigenvalues?
Let
be an equal superposition of the powers of
Then
which means we leak out information about the period
This is the change-of-basis given by the QFT.
qft4 = QuantumCircuit(4)
qft4 = qft(qft4, 4)
qft4.draw(output="mpl", style="iqp")
(zero ^ zero ^ zero ^ one).evolve(U_f).evolve(qft4).draw("latex")
Final fact: Sum of #
One final observation is that
Summary#
We reviewed the quantum modular exponentiation algorithm.