Zhengfeng Ji
Seminars on Quantum Computing is a quantum computing course designed for undergraduate students in the computer science.
This is an incomplete set of notes prepared by Zhengfeng Ji for the course.
What is quantum computing, or more generally, what is quantum information science?
The first example question in ChatGPT: Explain quantum computing in simple terms.
The answer I got was:
Quantum computing is a type of computing that uses the principles of quantum mechanics, the science of the very small, to process information. Instead of using classical bits, which can be either 0 or 1, quantum computers use quantum bits or qubits, which can be in multiple states at the same time.
This ability to exist in multiple states simultaneously is called superposition and allows quantum computers to perform certain calculations much faster than classical computers. In addition, quantum computers can also use a phenomenon called entanglement, where the state of one qubit is correlated with the state of another, to further enhance their computational power.
Quantum computing has the potential to solve some of the world's most challenging problems in fields such as cryptography, drug discovery, and climate modeling. However, building a fully functional quantum computer remains a major scientific and engineering challenge, and many of the applications of quantum computing are still in the experimental stage.
You can try DeepSeek V3 and you will get something similar or better.
They all describe the outline and motivation of this course well!
Quantum + Information: The second quantum revolution
The success of quantum mechanics. Laser, GPS, etc.
From passive understanding of the collective effects to active manipulation of individual particles.
History and highlights
a. Early history: Feynman 1982, Deutsch 1985, Deutsch-Jozsa 1992 b. Shor's factoring algorithm 1994 (breaks RSA) c. Quantum cryptography (QKD, Bennett Brassard 84) d. Quantum teleportation (Bennett et al., 1993) e. Simulation of quantum systems (Feynman's dream)
Current status
Primitive quantum computers are being built. Many players are racing to build quantum computers: Google, IBM, China, …
Different labs/companies are betting on different hardware routes: Superconducting qubits, ion traps, photonic systems, topological qubits, and more recently, neutral atom platforms.
Nowadays, there are programmable quantum computers with 50-1000 qubits.
Major problem: devices are noisy! The noise level
is around
Supremacy and simulation of Google and USTC
Sycamore, 53 qubits
Zhuchongzhi, 66 qubits
The biggest competitor to quantum computers are clever classical algorithms: In Nov 2021, a group from Chinese Academy of Sciences used tensor network algorithms to reproduce the statistics of the Google supremacy experiment using 512 GPUs in 15 hours.
Both Google and USTC have upgraded the system to battle against better classical simulation methods and hardware.
On the theory side: new algorithms, new protocols, fault-tolerant quantum computing, new insights on the power of quantum computers
More computer scientists get involved
Hype?
a. TIME's new cover: Quantum computers will transform our world—and create a 21st century "space race"
b. Quantum computing has a hype problem, MIT Technology Review, By Sankar Das Sarma.
Quantum computing startups are all the rage, but it's unclear if they'll be able to produce anything of use in the near future.
What you will learn in this subject
Is quantum computing hard to learn?
The mathematics is easy, the physics is hard.
There is a simple mathematical framework describing quantum mechanics with merely four postulates, about state space, evolution, measurement, and joint system, respectively, in both the pure state and mixed state settings.
The postulates are simple, but the truly amazing thing to note is how far these four simple postulates can bring us.
"Shut up and calculate!"
Reiterate over the four postulates from different perspectives.
Zhengfeng Ji, Yuan Feng, and Jianxin Chen
Office: 1-707, Ziqiang S&T Building
Research direction of Zhengfeng
Quantum computing, theory of computing.
Research direction of Yuan
Quantum computing, theory of programming, mathematical logic.
Research direction of Jianxin
Quantum computing, computer architecture.
Online: Wechat group, learn.tsinghua.edu.cn, email
Office hour: after each class
Homework on the quantum information basics. (40%)
Work on projects in groups and take an idea to the extreme (Given projects, or projects of your choice approved by your lecturers), write an essay, present your findings.
We will grade your project by its writing and format (10%), originality (20%), completion (10%), and presentation (20%).
Extra rule: If your project yields results deemed near-publishable by the teachers' evaluation, you will automatically receive an A+.
a. Quantum Computation and Quantum Information (Mike & Ike)
d. Foundations of Quantum Programming by Mingsheng (Tsinghua Online Access)
Computer science
Mathematics
Physics
Three basic statements about the physical world
Probability
Monotonicity
Single-slit case
Locality
Things can only propagate through the universe at a certain speed.
In physics, locality naturally emerges from Einstein's special theory of relativity, which implies that no signal can propagate faster than the speed of light.
Local Realism
Things have predetermined value, which depends on parameters in a local region.
Einstein: I like to think the moon is there even if I am not looking at it.
Church-Turing thesis
What is Church-Turing thesis?
TCS is mathematics but the Church-Turing thesis connects it to physics.
Information is physical.
Conversely: It from qubit.
Quantum mechanics and the above principles
Probability stays, yet monotonicity goes away.
Locality stays but realism is abandoned.
EPR and Bell's inequality.
Quantum computing does not falsify Church-Turing, but seriously challenges the extended Church-Turing thesis.
Watch this video.
Double-slit with an observer: which path did the electron take?
If there is a conscious observer, the distribution goes back to classical! That is the same as decoherence in a quantum system interacting with an environment!
Quantum mechanics is an (unusual) theory using probability.
A cat isn't found in a superposition of alive and dead states, because it interacts constantly with its environment. These interactions essentially leak information about the 'cat system' out.
This explains the difficulty of building a quantum computer. Quantum computers need to be isolated well from the environment yet still easy to manipulate.
Shor's factoring algorithm can be thought of as a large-scale interference experiment.
Born's rule
Probability stays but monotonicity goes.
God does play dice, and an unusual one.
Einstein liked inventing phrases such as "God does not play dice," "The Lord is subtle but not malicious." On one occasion Bohr answered, "Einstein, stop telling God what to do."
Instead of probabilities, quantum mechanics uses amplitudes.
Let
Example
Cancellation!
Consider the problem of flipping a coin.
Apply a transform
In general, the transform is a matrix of transition probabilities
Markov chain and stochastic matrix.
Now consider two independent coins. This leads to the tensor product very naturally.
More generally, the tensor product of two matrices
Consider the CNOT matrix.
It creates a correlation between the two coins.
Quantum mechanics is similar, except that it uses amplitudes.
A quantum state is a unit vector of
Finite dimensional spaces suffice for this course.
A qubit is a superposition of 0 and 1.
Quantum states are superposition of possibilities.
Dirac notation.
ket, bra (
Unitary.
Examples:
Why unitary? Unitary operators are the only operators that preserve the length of vectors.
一场从根上开始的革命 (by Mingsheng Ying)
Simulating physics with computers (by Richard P. Feynman)
18:01 Charlie Bennett - 1981 and the Beginning of Quantum Information
49:20 Peter Shor - Development of Quantum Algorithms and Error Correction
Probability, amplitude, and Born's rule
Two-slit experiment
A (classical) random bit the mixture of
A quantum bit (qubit) is a superposition state described by
amplitudes for
1-norm vs. 2-norm theory.
Linear algebra for probability
A (random) bit is represented as a vector
CNOT says if the control bit is
Tensor product arises naturally.
Binary symmetric channel as a matrix.
Linear algebra for quantum mechanics
Quantum gates
Unitary gates
Pauli
The Hadamard gate
In some sense, the most important quantum gate.
The Hadamard gate
It maps
Destructive interference (in the tree for
All quantum gates are changes of basis.
We can expand
There are different ways to measure in quantum!
What if we measure along another choice of basis? Say,
Decompose the state
Two views:
The projection picture on the circle.
Projective measurements.
Like calculating the probability of two independent random bits, we can use the tensor product to represent the state of multiple qubits.
It is now the tensor product of quantum states (vectors of amplitudes instead of vectors of probabilities).
Two-qubit states
A general two-qubit state is
It is the superposition of four possibilities.
Born's rule gives the probability of four outcomes.
In principle there's no distance limitation between the two qubits.
Let's say the first qubit is in Alice's hand. What happens if Alice measures it?
If Alice obtained
This is called the Partial Measurement Rule, which follows from the measurement postulate.
Two-qubit gates
Single-qubit gates as a two-qubit gate:
Applying the same single-qubit gate on the two qubits:
CNOT gate.
We need some facts from linear algebra to take our grasp of quantum mechanics to the next level.
Matrix entries
Hilbert space: vector space with an inner product.
What is an inner product
A concrete example is
Question: is this the only possibility?
Dirac notation
The norm is induced by the inner product (of the Hilbert space).
The normalization of
The decomposition of a state into basis
Then
Orthonormal basis and completeness relation:
If
Adjoints of operators
Let
In the matrix form,
Matrix
Example: What is the eigenvalues and eigenvectors of
Spectral decomposition theorem
Theorem. Any normal operator
Families of diagonalizable matrices
Matrix | Condition | Eigenvalues |
---|---|---|
Normal | Complex | |
Hermitian | Real | |
Unitary | Phase | |
Projection | ||
Reflection |
For
Example:
State
The state of a closed quantum system can be described by a unit vector in a Hilbert space (called the state space).
Closed: no observer, no leak of information to the environment!
If a "particle" can be in one of the
such that
Evolution
The discrete time evolution of the closed system can be described
by a unitary operator. If the state at time
It also follows from the Schrödinger equation
Take
Measurement
Composite system
The state of a composite system whose components have states
The measurement postulate
Quantum measurements are described by a collection
The index
(Compare the
If the state of the system is
The state after the measurement is
Why this general form?
It is essentially Born's rule when we use ancillary systems and apply a joint unitary operation.
It is known as the Naimark theorem.
Hint: Consider a unitary
Special case: projective measurement if
Observable: an operator that models the observation of a physical quantity.
For any Hermitian operator
where
So the average value
Measurement collapses the state.
The three polarizer "paradox".
Gates are:
Invertible
This means that unitary gates never erase information. Compare this with classical gates!
Deterministic
Nothing is random in the application of a quantum gate.
Continuous
There is a unitary operation that represents the evolution of a smaller period of time.
Explains the necessity of using complex numbers.
What is the square root of the
Measurements are:
Irreversible
We cannot go back to the state before measurement in general!
The superposition state (wave function) collapses.
Probabilistic
Born's rule.
Discontinuous
The collapse of the wave function in measurement is considered instantaneous!
How does quantum mechanics reconcile these two conflicting operations? Born's rule!
Gates preserve the 2-norm, and measurements give the probabilities determined by the 2-norm.
If you want to think more about superposition, the lecture by Allan Adams on superposition is highly recommended.
Quantum measurements are described by measurement operators
The probability that
The post-measurement state given outcome
An observable is a Hermitian operator whose eigenprojectors form a set of measurement operators indexed by the eigenvalues.
How do we process information using the four postulates?
Boolean functions, Boolean circuits, and Boolean formulas
A Boolean function is function
There are
A Boolean circuit is a model of computation using gates and wires.
A Boolean formula is a Boolean circuit where all gates have
fan-out at most
Functional completeness
A set of Boolean functions
Shannon formula:
Disjunctive normal form (sum of minterms):
Quantum circuit is our new language for describing quantum information processing.
Reversibility implies that the quantum circuit looks more regular (the same number of input and output qubits).
From left to right: initial state
Reverse the order when writing them in an equation:
Multi-qubit gates CNOT, C-U, CCNOT (Toffoli) in circuit diagrams.
What does it mean to apply a single qubit
Prepare a classical bit string
Bell state preparation.
Qubit is the quantum analog of bit and is, therefore, the simplest yet most important concept in quantum information processing.
Some noteworthy examples of states are:
Single-qubit states
Examples of single-qubit states
Quantum theory is a
Global phases do not matter and so we can write
Pure single-qubit states are on the Bloch sphere.
Before discussing mixed states in the Bloch sphere, we review the Pauli operators.
Pauli operators are unitary, Hermitian, and traceless.
What are their eigenvalues and eigenvectors?
Pauli operators as observables.
Commutation and anti-commutation relations of Pauli operators
For any unit vector
It is unitary, Hermitian, and traceless
For pure state
What are the eigenvectors of the above operator?
The coordinate of
It would be more natural first to define the
It explains the
Pauli
The example of the
How about
We do quantum information processing simply by rotating the qubits in our system!
Hadamard
Rotations through
In particular,
Rotations along
Any single-qubit unitary operator
for some
(Z-Y decomposition) Any single-qubit unitary
The computational (standard) basis measurement (
Is the state
(Born's rule) When we measure
With probability
With probability
Hadamard basis measurement (
Is the state
When we measure
With probability
With probability
Measurement operators
Why is it called the Hadamard basis measurement?
A projective measurement in the direction of
Note that
Measurement operators
Check that
Someone sends you a box, which is either a dud (empty box) or a
bomb attached to a quantum device that will trigger the explosion if
it measures a
Not very interesting
Dud: No explosion, measures
Bomb: 50% explosion, 25% measures
a. Start with
Use
b. Repeat
Dud: No explosion, measures
Bomb:
This is known as the quantum Zeno effect.
Entanglement is yet another peculiar quantum phenomenon along with superposition and measurement.
Superpositions of 00, 01, 10, 11
Tensor products
Tensor product of two matrices
Vector representation
Normalization condition
CNOT, SWAP, Controlled-
Circuit identities
Control vs. target
CNOT and single-qubit gates are all you need for universal quantum computing.
…, then they can no longer be described in the same way as before, viz. by endowing each of them with a representative of its own. I would not call that one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought. By the interaction the two representatives [the quantum states] have become entangled.
Four Bell states
The first index determines the sign; the second determines the parity.
Prepare the Bell states
The Bell states are also known as the EPR states, and we often
use
Singlet state
The other three states are all symmetric and span the symmetric subspace of the two-qubit state space.
It is easy to verify that this state is not a product of single-qubit states!
A picture of entanglement.
Basic rules of quantum mechanics imply the existence of EPR, arguably what troubled Einstein the most in quantum mechanics! It is what he called the 'spooky action at a distance'.
Consider two players Alice and Bob sharing an EPR state. Alice brings her particle to the moon while Bob stays on earth.
Fact: If Alice measures her particle, she instantaneously
knows whether Bob's state is
Is it a big deal?
It is not very different from a pair of two perfectly correlated classical bits.
A pair of gloves in two boxes.
EPR considers other possibilities: Alice can measure in a different basis.
There is another way to open the box.
We have measured
Method I.
Method II. Write EPR state
The conclusion is that Alice will instantaneously know
whether Bob's post-measurement state is
Consider two situations. In the first, Alice measures in the
standard basis, she will obtain
It looks as if Alice's measurement choice affects Bob's final state! Would it allow Alice to send information instantaneously to Bob?
What are the states of Bob in the two situations?
Bob's view and Alice's view.
The mixed state framework will help us to answer the question and see why this won't allow superluminal communication.
In the first situation, Bob's state is in an equal distribution
over
Let's generalize a little bit and consider a distribution of pure
states described by an ensemble
Consider a quantum measurement
We can rewrite it using cyclic property of the trace as
We call
the density matrix of the ensemble. The probability is determined by the density matrix, so it makes sense to use the density matrix to describe the state of the system.
We now go back to the EPR paradox. When Alice measures
If Alice measured
So even though the two ensembles look very different, the density matrices in the two situations are the same. It means that no measurement on Bob's system can tell the two cases apart. This makes perfect sense as the state of Bob should not change when Bob has done nothing to his system.
It explains why density matrix is more fundamental then ensemble of quantum states.
No superluminal communication is possible using the strategy above!
Mathematically, a density matrix is positive
semidefinite and of trace
Any pure state
Example: The density matrix for
The spectral decomposition of a density matrix
gives a possible ensemble
Probability can be considered a special case where the density matrix is diagonal.
The state is now a density matrix.
Evolution:
Measurement:
Tensor:
Define an inner product on the
Together with
For all
The positive semidefinite condition is equivalent to
The Bloch sphere has all valid single-qubit states.
What are the states of the north pole, the origin, and
From coordinate
Conversely, given the density matrix
Classical probability over a bit can be represented as diagonal density matrices corresponding to the line segment between the north and south poles.
Summarize: Things that can be identified with point
When we measure
With probability
With probability
What is the state of
Let
We need an effective representation of the state on
Let
which is a linear functional of
The partial trace is defined by
Extend by linearity.
The reduced density matrix
What is the partial trace of the EPR state?
The reduced density matrices of
For any mixed state
Use the spectral decomposition theorem again!
Example: The EPR state is a purification of
Mixed states arise when we lose control of a system!
Homework I
Problem 3 about computing
Problem 4
Spectral decomposition
Consider a special case where
Let
This means that
Consider subspace
We prove that
In standard textbooks, it says that
In this form,
and
Measurement
Projective measurements
Measurement operators are projectors such as
Note that
A set of projectors
General measurement satisfies
When we don't care about the post-measurement state, we
consider measurement operators
The completeness condition is
The probability that
They are called positive-operator valued measure (POVM).
(Schmidt Decomposition). For a bipartite pure
quantum state
where
The meaning of the theorem says that, up to a change of local basis, an entangled state can be written as
Hint: Consider the singular value decomposition of matrix
EPR as a mirror!
For any matrix
What are the Schmidt coefficients of the Bell states?
How about product states?
Thanks to this theorem, the theory of pure bipartite entanglement is well established.
Local operation and classical communication (LOCC)
Nielsen's Theorem
Let
Theorem (Nielsen). There is an LOCC transforming
The condition
A simple corollary is that there is an LOCC transforming an EPR pair to an arbitrary entangled pair of qubits.
EPR: Maximally entangled states.
Superpositions of 000, 001, 010,
GHZ state
W state
Entanglement is a resource for many quantum information processing tasks
Now utilized for good at a distance of at least 1200km (Mozi satellite).
Quantum entanglement—physics at its strangest—has moved out of this world and into space. In a study that shows China's growing mastery of both the quantum world and space science, a team of physicists reports that it sent eerily intertwined quantum particles from a satellite to ground stations separated by 1200 kilometers, smashing the previous world record. (Science, 15 JUN 2017)
A qubit is a unit of quantum information storing the quantum state of a two-level physical system.
Quantum information is more general than classical information. We can store a bit in a qubit. But to store a qubit, it may require an infinite number of bits.
Consider an encoding
Promise: The system is in one of the two states
Problem: Decide which is the case.
Measurement is the only bridge between the quantum and
classical worlds. So we use a measurement with measurement operators
The optimal
In the qubit case, we write
The minimal error probability is therefore
The amount of information one can store and reliably read from a qubit is only a single bit.
The states
Non-orthogonality is the key issue.
What is information? What is quantum information?
We can store the whole Internet in a single qubit, but we cannot reliably read information out.
For a quantum state
The eigenvalues of
Mutual information
Theorem. Let
The right-hand side is called Holevo
We will prove a poor man's version of Holevo's theorem.
Let
In expectation the success probability is therefore
Let
The quantum one-time pad works as follows:
For a player who does not know
Unknown quantum states cannot be copied.
There is no unitary transformation
Compute the inner product.
Note:
Given a large number of i.i.d samples of quantum state
In the single-qubit case,
For example, to estimate
Note that the standard deviation is
Multiple qubit case is similar:
where the summation goes over
Check that
But it's a summation of
In the lab, it would take days to tomography a system of more than 10 qubits.
Theorem. The sample complexity for tomography is
To make things worse, each term needs high precision for the triangle inequality to give meaningful bounds.
There are
How do we even know the quantum device works as expected when tomography of its state is impractical?
We need to estimate 15 real numbers
I | X | Y | Z | |
---|---|---|---|---|
I | 0 | 0 | 0 | |
X | 0 | -1 | 0 | 0 |
Y | 0 | 0 | -1 | 0 |
Z | 0 | 0 | 0 | -1 |
For
For all other
Note that in this simple case, it suffices to check the
The singlet state is the unique state stabilized by
We have two players, Alice and Bob.
Alice and Bob share an EPR state.
Alice also has an input qubit given in some unknown state
Classically, there are two methods.
She wants to transfer this qubit to Bob using classical communication only.
Even if Alice knows the description of the state
To describe the state, we need to specify two real numbers!
The teleportation protocol needs to transfer two bits from Alice to Bob by consuming the shared EPR state.
We name the qubit in the shared EPR state between Alice and Bob and the input qubit as A, B, and C, respectively.
The Bell states form an orthonormal basis for the two-qubit
system
The protocol is simple but very hard to find and only discovered in 90's (quantum mechanics was completely established in the 30's).
Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
[C. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres and W. Wootters, '93]
The Origins of Quantum Teleportation - Charles Bennett
What is it that they don't have that they need that would enable them to do as well if they were in separate locations than if they were in the same location.
… So then we realized that by sharing entanglement between the two observers and by permitting them to communicate, you could simulate being in the same place.
Before Alice's measurement, the state is
Expand the state using the Bell basis, we have
If it is the first you see this, you may feel a bit confused about how we get the above expansion. The key is to use linearity to do this on product state terms and take the sum. Alternatively, you may consider multiplying
If the measurement has outcome
Measurements can be delayed to the end.
Proof: Use controlled gates to simulate classical control.
For
Tensors are generalizations of matrices.
Matrix
A rank-k tensor
Tensor diagrams.
We use a circle (or other shapes) to represent the tensor and
The dimension of each index is the number of different values it takes.
Tensor contraction generalizes matrix multiplication.
If two indices have the same dimension, the contraction operation identifies them and sums them over.
Trace in tensor network!
States, gates, and measurements are all tensors
Quantum circuits are tensor networks!
Teleportation as a tensor contraction:
The EPR state is a wire in the tensor picture;
We can move the tensor node freely along the wires.
Bob gets the one-time pad of Alice input qubit
as
Specifying quantum states using operators:
Measure both qubits in the Hadamard basis (
The Bell measurement is the same as measuring the
We can measure both as they are compatible.
Back propagation of operators
Teleportation is explained in the stabilizer framework.
What if the input state on C is part of a larger system
After the teleportation, the state on
A special case is when
It is known as the Entanglement Swapping protocol.
Would teleportation allow faster-than-light quantum transmission?
Bob has one-time padded quantum information without the two bits.
Would teleportation allow the cloning of quantum information?
Did the Bell measurement learn anything about the input state?
The four Bell states can be transformed to each other locally.
The four Bell states are orthogonal to each other and are therefore perfectly distinguishable.
A scheme for sharing classical secrets (2 bits) among two players (each holding one qubit).
Question: is it possible to share quantum secrets?
Teleportation, superdense coding, and many other protocols use EPR and entanglement as resource, without which the protocols cannot be carried out.
They motivated the study of entanglement as a new type of resource.
How do we quantify the amount of entanglement needed for a certain task?
A mixed state
Separable states are preparable using LOCC only
Wide range of applications
[M. Ying, L. Zhou, and Y. Li, Reasoning about Parallel Quantum Programs, '18], [C. Piveteau and D. Sutter, Circuit Knitting with classical communication, '22]
How to check if a mixed state is separable or not?
Partial transpose
(PPT condition). If
Check that the
The PPT condition is a necessary and sufficient condition for
separability only for
In general, it is NP-hard even to approximate with
[S. Gharibian, Strong NP-Hardness of the Quantum Separability Problem, '08]
Distillable entanglement and entanglement cost
Distillable entanglement
Entanglement cost
If
Bound entanglement: entangled states which cannot be distilled exist!
[Horodecki
Quantum networks
Teleportation empowers entanglement swapping and quantum repeaters.
Gate teleportation
[Aliferis and Leung, Computation by measurements: a unifying picture, 2014]
Port-based teleportation
We have seen many quantum gates such as
Toffoli
Fredkin
Both Toffoli and Fredkin are classically universal.
Simulate
Reversible classical computation and Landauer's principle
Energy consumption and irreversibility in computation
In the scenario where a computer erases bit of information, it
results in the dissipation of energy into its surrounding environment.
The minimum amount of energy that is released is proportional to
Does computation have to consume energy?!
It's possible to perform classical computation reversibly (using Toffoli or Fredkin).
Uncompute technique
Clean the computational garbage!
A set of quantum gates is universal if all other unitary operators can be generated exactly (or approximately) from that set.
Quantum computers are digital.
Approximation in the sense of the following distance
Example:
CNOT and single-qubit gates (exact);
CNOT, H, T (approximate);
Toffoli, H (weakly universal).
Complex numbers are essential for quantum mechanics but not for quantum computing.
With an extra qubit, it is possible to map a circuit
Trick:
According to Wikipedia, it was first announced by Robert M. Solovay in 1995 and independently proven by Alexei Kitaev in 1997.
Let
Lemma. Let
Note that the lemma is not easy to use iteratively as the
scaling of
The closedness condition under inverse is not needed anymore.
Suppose
Proof: By the triangle inequality and unitary invariance of the operator norm,
This means that for a circuit of
Let
This implies that we can efficiently perform the following transform
The superposition principle then implies that we can efficiently prepare
Use the uncompute technique.
Phase oracle: If
We add a
To implement the standard oracle, we may need a controlled phase oracle.
Let
We are given oracle access to
Problem: find out which of the above two cases is true.
A classical algorithm will need
Quantum parallelism and cancellation!
After Step 2, the state is
The action of
So after Step 3, the state is proportional to
The probability of observing
Bernstein-Vazirani algorithm.
Given oracle access to
Problem: Find
Analysis
Similar to the analysis of the Deutsch-Jozsa algorithm.
Before measurement, the state is
Any classical algorithm (deterministic or randomized) needs
The final answer consists of
Simon's algorithm is the main inspiration for Shor's factoring quantum algorithm.
It shows that quantum computers are provably exponentially more efficient (in terms of the number of queries) than bounded-error randomized algorithms.
Simon's problem setup:
Oracle
Problem: Find
Note that the function
The state on
for some random
It is the superposition of preimages of
After Step 1.3 each iteration, the state on
The measurement will output a random
Step 1.2 is not necessary.
Each
To determine
If the dimension of
Simon's algorithm queries the oracle
Yet any classical algorithm needs
Upper bound: By the birthday paradox, we expect to find
Lower bound: Any classical (randomized or deterministic)
algorithm needs
We say that a sequence
This excludes at most
For all
Let
The discrete Fourier transform transforms a function
to another function
Here,
The normalization factor makes the map a unitary operator!
A transformation on a sequence of
An important tool in classical signal processing.
Cooley–Tukey algorithm, from
Gauss (1805)!
Assume for simplicity
Consider the even and odd parts of
Recursive structure: for
What about the second half? For
The recursion relation is
FFT: compute the fast Fourier transform (recursively) on the even and odd parts respectively and combine the results using the above rule.
For function
Quantum Fourier transform maps the superposition
Verify that
Recall that quantum computation is about the processing of superposition states.
In QFT, we transform the amplitudes by DFT.
The QFT is a unitary transform:
Hadamard is the smallest Fourier transform (N=2)!
Hadamard and Toffoli are quantum universal.
Use the recursion in a quantum way.
Apply QFT of
Then do some post-processing.
Cheating?! No!
After the QFT on the first
Define function
Apply Hadamard to the last qubit, we get
Move the last qubit to the first by SWAP gates, and we have
The last step is needed because we need
We have shown an efficient implementation of QFT.
Complexity is
A result shows that, if small rotations are omitted, QFT still
works approximately and has complexity
Do not expect it to be useful in most problems of signal processing!
You cannot read out the values of the amplitudes.
You may select one of the provided topics and work in a group of up to three students. While not mandatory, students are strongly encouraged to pursue projects that contribute something novel, whether through a new perspective, innovative methods, or original algorithms.
Topic Selection Rules
Each topic can be chosen by at most two groups. Selection is on a first-come, first-served basis (先到先得).
After making your choice, please contact the teaching assistant via WeChat as soon as possible to secure your topic.
Contribution statement
The final submission must explicitly state each team member’s role, responsibilities, and specific contributions (e.g., theoretical analysis, implementation, experiments, writing, etc.).
Evaluation Criteria
Your project will be evaluated based on the following components:
Understanding
Writing (Research Paper Submission) Your written submission should follow a structured research paper format, including:
Submission Timeline:
In the final submission, please clearly state your individual contributions to the project.
Presentation (Week 16)
Originality
T1: Quantum Algorithms and Sparse Optimization
T2: IQP Circuits, Different Constructions and Noise Effects
T3: Resource Estimation for Proof of Quantumness
T4: Robust Combiners for Quantum Cryptographic Primitives
S1: Classical simulation of quantum circuits
S2: Birkhoff-von Neumann Quantum Logic
S3: Quantum Circuits and Polynomials
S4: Game Designed for Quantum Computing
C1: Quantum Error Correction Codes with Transversal Clifford Gates
C2: Exploration of Error Correction Algorithms for Quantum Dynamic Codes
C3: Gate Scheduling for Syndrome Measurements
In phase estimation, we have access to
controlled-
The problem is to estimate the phase
Inverse Fourier transform
Phase estimation is a powerful quantum algorithmic subroutine used in many other quantum algorithms.
To get an
Prepare state
Apply unitary
Apply an inverse quantum Fourier transform on the first register.
If
The first register is a good approximation of
The approximation will have
If
2015 Turing Award
New directions in cryptography
Given a cyclic group
The discrete logarithm
Important for classical cryptography (Diffie-Hellman key exchange)!
We can completely break the protocol, if we can solve the
discrete logarithm for
Yet, no efficient classical algorithm is known.
We attack the protocol by giving a quantum algorithm for
computing the discrete logarithm of a given
Consider the following unitary.
It is possible to implement controlled-
Define states
Use phase estimation!
How do we prepare the eigenstate
It is not easy as the phase
It won't work if we prepare
Forgetting quantum information coherently (
We can sample a random pair of
Factoring has been widely studied, and no classical algorithm is known.
The best known classical algorithm runs in time
People believe factoring is hard and use it to construct public-key cryptography.
Rivest, Shamir, and Adleman receive 2002 Turing Award for this.
Factoring is in BQP.
Shor's algorithm for factoring runs in
A challenge to extended Church-Turing thesis:
Any efficient computation performed on a physically realistic model can be carried out efficiently on a Turing machine.
How did Peter Shor discover his algorithm?
Knowing the period of
The smallest non-zero
If
Then
Number theory: The condition above happens with probability
Find the period of
The period can be huge, and the problem is believed to be classically hard.
Phase estimation applied to
Some eigenvectors of
How do we prepare the eigenstate
We don't know how to prepare
Yet, we have
We can obtain high precision of the phase
Use continued fraction algorithm to find
Suppose
Then the continued fraction algorithm for
Some hidden detail: Need a minor fix when
The development of Simon's and Shor's algorithms motivated the quantum algorithmic framework called hidden subgroup problem (HSP).
It generalized the technique to a lot more problems with group (algebraic) structures.
Simons problem:
Theorem: any finite abelian group is isomorphic to a direct product of cyclic groups.
The abelian HSP problem is completely understood.
Most of the non-abelian cases are open with a few exceptions.
A famous open problem is the dihedral subgroup problem, for
which the best quantum algorithm (Kuperberg's algorithm) runs in time
Shor's algorithm breaks the RSA public-key cryptosystem if large-scale quantum computers can be built.
Similar algorithms can break elliptic-curve based public-key cryptography.
Post-quantum cryptography is emerging.
NIST PQC standardization process announced the third-round candidates in July, 2020 and the candidates to be standardized in July, 2022.
Year | Public-Key encryption/KEMs | Digital signatures | |
---|---|---|---|
2020 | Classic McEliece (Code-based) | CRYSTALS-DILITHIUM (Lattice-based) | |
2020 | CRYSTALS-KYBER (Lattice-based, LWE) | FALCON (Lattice-based) | |
2020 | NTRU (Lattice-based) | Rainbow (Multivariate) | |
2020 | SABER (Module Learning With Rounding) | ||
2022 | CRYSTALS-KYBER (Lattice-based, LWE) | CRYSTALS-DILITHIUM (Lattice-based) | |
2022 | FALCON (Lattice-based) | ||
2022 | SPHINCS+ (Hash-based) |
Both Shor and Grover were at Bell Labs at that time.
Suppose you have a Boolean function
We know that there is one and only one input
We call this
How many queries to
Classically
In 1996, Grover gave a quantum algorithm that makes
How?! It's not very different from Elitzur-Vaidmen.
This marks the beginning of an interesting line of research on quantum algorithmic techniques different from QFT and HSP.
Remark: Grover's algorithm requires the oracle or QRAM (for database search).
Define Grover iterate as
where
An example for
Good state
The uniform superposition state
The Grover iterate consists of two reflections which generate a
rotation of
After
Choose
This is known as BBBV (Bennett-Bernstein-Brassard-Vazirani), proved even before Grover's algorithm where the authors tried to show that there shouldn't be quantum polynomial time algorithms for NP-hard problems.
Quantum algorithms need
There are now many proofs for this fact and there is an advanced theory called quantum query complexity answering related questions.
A quantum query algorithm for solving the search problem has the form
Hybrid argument proof idea:
First, consider a case where
There will be an
If we reprogram the oracle so that
We use a hybrid argument to prove the claim.
Consider Hybrid
Then
There is an
By Cauchy-Schwarz,
It is easy to show