MULT90063 Introduction to Quantum Computing
Lecture 13 – Quantum Supremacy
11.1 Boson Sampling
11.2 IQP Problem
Copyright By PowCoder代写 加微信 powcoder
11.3 Google’s pseudorandom circuits
Lecture 14 – Errors
12.1 Quantum errors: unitary and stochastic errors 12.2 Randomized Benchmarking
12.3 Purity
Quantum Supremacy and Errors
MULT90063 Introduction to Quantum Computing
Quantum Supremacy
Lecture 13
MULT90063 Introduction to Quantum Computing
Determining supremacy?
On February 10, 1996, Deep Blue beat Kasparov under tournament regulations. In the subsequent 1997 rematch, Deep Blue won the series.
MULT90063 Introduction to Quantum Computing
Quantum supremacy in the news
https://www.wired.com/story/google-alibaba-spar-over- https://www.newscientist.com/article/2176575-google-just-made-it-much-harder-to- timeline-for-quantum-supremacy/ build-a-serious-quantum-computer/
MULT90063 Introduction to Quantum Computing
Google claims quantum supremacy
https://www.theverge.com/2 019/10/23/20928294/google- quantum-supremacy- sycamore-computer-qubit- milestone
MULT90063 Introduction to Quantum Computing
What is quantum supremacy?
Quantum supremacy is using a quantum computer to solve a problem which classical computers practically cannot.
MULT90063 Introduction to Quantum Computing
Algorithms for quantum supremacy
Implementing large scale factoring would demonstrate quantum supremacy, but that would require a very large (potentially millions of qubits) quantum computer. In the short term we will only have access to NISQ devices.
Three quantum algorithms that can be used to demonstrate quantum supremacy with 50- 100 qubits:
• Boson Sampling
• Instantaneous Quantum Polynomial-Time circuits (IQP)
• Pseudorandom circuits
Intermediate Scale (50-100 qubits) Quantum devices
MULT90063 Introduction to Quantum Computing
HOWTO quantum supremacy
Pick a problem which is:
qAs easy as possible for a quantum computer
qAs hard as possible for a classical computer to simulate
MULT90063 Introduction to Quantum Computing
Boson Sampling
MULT90063 Introduction to Quantum Computing
A little physics experiment…
n single photon sources
Linear Optics (ie. beam splitters)
You won’t need to know the physics of this device.
n2 output modes.
Can a classical computer produce samples from the output which mimic the quantum device?
MULT90063 Introduction to Quantum Computing
Quantum Pachinko
Single photon in
Beamsplitters Wall
Single photon out Path of a photon
MULT90063 Introduction to Quantum Computing
One single path
We can write out a matrix: If a single photon enters in mode x, what is the amplitude it will have at output y?
Unitary matrix
… … an2 an3
Input modes
Linear Optics (ie. beam splitters)
a22 a23 U=64a32a33
… … … … …
a2n 7 a3n 75
Amplitudes of output modes
MULT90063 Introduction to Quantum Computing
Many paths
If we have two input photons:
What is the amplitude associated with being detected in output modes 1 and 3?
Input modes 3
a23 . . . a2n 7 Amplitudes
7 of output
4 … … … 5modes an3 … ann
Linear Optics (ie. beam splitters)
a13 … a1n
a33 … a3n
Amplitude of photons in locations 1,3:
a11a32 + a12a31
MULT90063 Introduction to Quantum Computing
Many paths
In general take the submatrix corresponding to a particular input and output, and find its
permanent:
26 a13 … 6 a21 a22 a23 …
U=6 a33 … 4 … …
perm(A) = ai, (i) c d
a1n 37 a2n 7
Submatrix defined by the inputmodesandoutput
a31 a32 … …
… 5 modes
an1 an2 an3 …
The resulting amplitude is the permanent of the submatrix:
X Yn A = a b ,
Same as determinant, but with no subtraction, all addition.
perm(A) = ad + bc
MULT90063 Introduction to Quantum Computing
Complexity of finding permanent
Unlike determinants, finding a permanent of a matrix is a surprisingly difficult computational problem.
#P is the set of counting problems associated with decision problems in NP.
Finding the permanent is a #P complete problem.
NP: Is there as a satisfying assignment of variables to this 3SAT problem?
#P: How many satisfying assignments of variables are there to this 3SAT problem?
NP: Is there a travelling salesman path with distance less than d?
#P: How many travelling salesman paths are there with a distance less than d.
Calculating amplitudes and probabilities for Boson sampling is a hard classical problem!
MULT90063 Introduction to Quantum Computing
Some classical complexity classes
Informally:
P: Problems which can be solved in polynomial time
NP: Problems which can be checked in polynomial time (ie. they have an efficiently verifiable proof)
#P: Problems which count the number of solutions in NP
MULT90063 Introduction to Quantum Computing
The polynomial hierarchy
Very quick introduction: Given an oracle in some complexity class which evaluates instantly, what problems can we now evaluate in polynomial time?
Polynomial time algorithm
With access to an oracle which can instantaneously evaluate functions in P
But a polynomial time algorithm with an NP oracle appears to be more powerful than both P and NP:
We can recursively define complexity classes this way, with oracles which increase in
strength at each level. This whole hierarchy is known as the Polynomial Hierarchy, PH.
If, at some level, providing the oracle didn’t lead to a superset of problems, the polynomial hierarchy would “collapse”. Computer scientists don’t think this happens.
MULT90063 Introduction to Quantum Computing
Sampling is also hard to simulate
Calculating amplitudes and probabilities for Boson sampling is a hard classical problem!
Calculate the permanent of the submatrix:
X Yn 2Sn i=1
perma b =ad+bc cd
We don’t technically have to calculate the probabilities explicitly. Maybe we can
sample from the probability distribution?
No – this would result in a collapse of the Polynomial Hierarchy.
Not proven, but like P=NP, computer scientists generally don’t expect the polynomial hierarchy collapses.
MULT90063 Introduction to Quantum Computing
HOWTO quantum supremacy
Boson Sampling is a problem which: q“Easy” to implement using linear optics
qHard for a classical computer to simulate – Polynomial Hierarchy would collapse
MULT90063 Introduction to Quantum Computing
IQP Circuits
Instantaneous Quantum Polynomial-Time
MULT90063 Introduction to Quantum Computing
IQP Circuits
(5) Measure
(1) Hadamard gates Equal superposition
(2) Random single qubit phases
(3) Random two qubit phase gates between every pair
(4) Interfere all the resulting states
MULT90063 Introduction to Quantum Computing
Random Phases
Each of these Tm gates Is a rotation (around z) by a multiple of π/4:
Tm =cos✓km⇡◆I+isin✓km⇡◆Zm 8 ✓ km⇡◆ 8
Tm=Rz 4 onthemthqubit
Where km is an integer chosen uniformly at random between 0 and 7. This is equivalent (up to a global phase) of applying a T gate km times.
MULT90063 Introduction to Quantum Computing
Random Joint Phases
Each of these Tmn gates Is a joint phase rotation by a multiple of π/8:
Tmn =cos✓kmn⇡◆I+isin✓kmn⇡◆ZmZn 88
Where km is an integer chosen uniformly at random between 0 and 7.
In the lab we can implement a similar algorithm with controlled Tmn gates.
MULT90063 Introduction to Quantum Computing
“Instantaneous”
All of these phase gates commute
The order which you apply the single and two qubit phase gates doesn’t
matter. They commute with each other, so can be applied in any order.
ZT2=1 0 10 =1 0 0 10i 0 i
T2Z=10 1 0 =1 0 0i 0 1 0 i
Diagonal gates commute
MULT90063 Introduction to Quantum Computing
Collapse of the polynomial hierarchy
Aim: To sample from the output of this circuit. Easy for a quantum computer.
If this could be done efficiently using a classical computer, it would imply the collapse of the polynomial hierarchy (and so isn’t expected to be possible).
Practically, classical simulations are limited to <50-70 qubits (for low error rates).
MULT90063 Introduction to Quantum Computing
Pseudorandom Circuits
MULT90063 Introduction to Quantum Computing
The circuit
Hadamards to give equal superposition
Controlled-Z gates to provide entanglement in a regular pattern
A random single qubit gate between every pair of CZ gates.
MULT90063 Introduction to Quantum Computing
Square Root X and Y
In the previous slide, we simply have that
X 1 / 2 = R x ⇣ ⇡2 ⌘
Y 1 / 2 = R y ⇣ ⇡2 ⌘
and similarly,
MULT90063 Introduction to Quantum Computing
Schedule of CZ
From Boixo et al, https://arxiv.org/pdf/1608.00263.pdf, 2016.
MULT90063 Introduction to Quantum Computing
Sampling is hard
Once again, the aim of the algorithm is to sample from the measured values.
If this were possible to do efficently classically, it would imply a collapse of the polynomial hierarchy.
In practice, simulating ~45 qubits for this problem is hard (note: need high depth circuit)
MULT90063 Introduction to Quantum Computing
What do you need for quantum supremacy?
• Many qubits (>~50)
• Large depth circuit (>~100)
• Entanglement, high T gate count
• Low error rates (<1%)
MULT90063 Introduction to Quantum Computing
60 Qubit Simulations of Shor’s algorithm
Using MPS, wrote parallel code were able to do large scale simulations of Shor’s algorithm.
Source: Dang, thesis, 2017
MULT90063 Introduction to Quantum Computing
Simulating Google’s Pseudo-Random Circuits
Depth of the circuit is equivalent to the number of timesteps
MULT90063 Introduction to Quantum Computing
Importance of Depth
Source: Dang, thesis, 2017
MULT90063 Introduction to Quantum Computing
Effects of Errors on IQP simulation runtime
MULT90063 Introduction to Quantum Computing
What do you need for quantum supremacy?
• Many qubits (>~50)
• Large depth circuit (>~100)
• Entanglement, high T gate count
• Low error rates (<1%)
MULT90063 Introduction to Quantum Computing
Lecture 13 - Quantum Supremacy
11.1 Boson Sampling
11.2 IQP Problem
11.3 Google’s pseudorandom circuits
Lecture 14 - Errors
12.1 Quantum errors: unitary and stochastic errors 12.2 Randomized Benchmarking
12.3 Tomography
Quantum Supremacy and Errors
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com