Towards a Complexity Theory ��for the Quantum Age
Henry Yuen
Columbia
Image credit: Dall-E
What is the Quantum Age?
Quantum computers are commonplace.
They compute on quantum data.
They communicate over a quantum network.
What are the computational problems of the Quantum Age?
How do we reason about their complexity?
Wait a minute…
…don’t we already have this?
Symposium on Theory of Computing 1993
30 years of Quantum Complexity Theory
30 years of Quantum Complexity Theory
A theory of “classical input/classical output” problems
Classical
Input
Quantum
Model of Computation
Classical
Output
30 years of Quantum Complexity Theory
A theory of “classical input/classical output” problems
Integer N
Quantum Computer
Factors p, q
Example: Factoring
30 years of Quantum Complexity Theory
A theory of “classical input/classical output” problems
Local Hamiltonian H
QMA verifier-prover protocol
Ground energy ± ℇ
Example: Local Hamiltonians problem
With classical input/classical output problems, we can compare classical vs quantum models of computation.
It also allows us to connect Quantum Complexity Theory with Classical Complexity Theory.
e.g., “BosonSampling is hard for classical computers unless the polynomial hierarchy collapses”
Quantum in, quantum out
In the Quantum Age, quantum computers will perform tasks that
don’t make sense on classical computers.
Quantum in, quantum out
Local Hamiltonian H
Ground state of H
Example: Preparing complex quantum states
In the Quantum Age, quantum computers will perform tasks that
don’t make sense on classical computers.
Quantum Computer
Quantum in, quantum out
Noisy quantum state
Denoised state
Example: Correcting noisy quantum information
In the Quantum Age, quantum computers will perform tasks that
don’t make sense on classical computers.
Quantum Computer
Quantum in, quantum out
Quantum state in�unknown phase
Quantum Computer
Phase label
Example: Classifying quantum phases of matter
In the Quantum Age, quantum computers will perform tasks that
don’t make sense on classical computers.
Quantum in, quantum out
These are natural tasks in the Quantum Age.
Can Quantum Complexity Theory explain when they are easy?
Or when they are hard?
Quantum in, quantum out
These are natural tasks in the Quantum Age.
Can Quantum Complexity Theory explain when they are easy?
Or when they are hard?
Recently, Quantum Complexity Theory has started looking incomplete.
Quantum information 101
Quantum information is different
The story of�quantum bit commitments
Bit commitments
Cryptographic analogue of putting a message in a sealed envelope that is opened later. A commitment protocol involves two phases, commit and reveal.
Committer
Receiver
…
Hiding security: commitment c does not reveal bit b to receiver.
Bit commitments
Cryptographic analogue of putting a message in a sealed envelope that is opened later. A commitment protocol involves two phases, commit and reveal.
Reveal phase: committer opens commitment c to reveal b.
Committer
Receiver
…
Binding security: committer cannot open to opposite bit 1 – b.
Security of commitments
Commitments are fundamental, used in multiparty computation and zero-knowledge protocols.
Security of commitments
Commitments are fundamental, used in multiparty computation and zero-knowledge protocols.
The security of commitments requires some computational assumptions, e.g. P ≠ NP.
If both parties can solve NP-complete problems, either �Hiding security or Binding security (or both) can be broken…
Security of commitments
Commitments are fundamental, used in multiparty computation and zero-knowledge protocols.
The security of commitments requires some computational assumptions, e.g. P ≠ NP.
If both parties can solve NP-complete problems, either �Hiding security or Binding security (or both) can be broken… ��…at least, if the scheme is classical.
Quantum bit commitments
What if the scheme takes advantage of quantum physics?
Committer
Receiver
Commit phase: Committer, receiver exchange quantum messages. �Afterwards, they can be entangled.
Hiding security: receiver cannot learn b by measuring her quantum state.
Quantum bit commitments
What if the scheme takes advantage of quantum physics?
Committer
Receiver
Reveal phase: they exchange more quantum messages. �Afterwards, receiver measures her state to verify commitment to b.
Binding security: even if committer deviates from the protocol, �receiver accepts 1 - b with very small probability.
Quantum bit commitments
In 1980s, cryptographers were fascinated by the possibility of unconditionally secure quantum commitment schemes.
This was motivated by quantum key distribution (QKD), �whose security is based only “on the laws of quantum physics”, rather than unproven complexity conjectures.
Some researchers (1993): We found it!
Lo, Chau/Mayers (1996): No you didn’t.
Quantum bit commitments
Lo, Chau/Mayers 1996: The security of commitment schemes �(even quantum ones) must rely on computational assumptions.
Lo, Chau/Mayers argument
Committer
Receiver
Lo, Chau/Mayers argument
Committer
Receiver
Suppose, for contradiction, that both Hiding and Binding security do not require computational assumptions.
Uhlmann’s theorem
Uhlmann’s theorem is central in quantum information: it quantifies how well one can locally transform one entangled state into another.
Uhlmann transformation on A
identity transformation on B
Lo, Chau/Mayers argument
Committer
Receiver
Lo, Chau/Mayers argument
Committer
Receiver
Complexity of Uhlmann transformations
Complexity of Uhlmann transformations
Based on classical cryptography we expect Uhlmann transformations to be difficult.
Breaking commitment �schemes
Inverting one-way functions
Implementing �Uhlmann transformations
Lo, Chau / Mayers (1996)
Classical commitment�construction from OWFs (e.g. Naor 1991)
Complexity of Uhlmann transformations
What about upper bounds on their complexity?
NP
Implementing �Uhlmann transformations
Breaking commitment �schemes
Not clear how Uhlmann transformations reduce to classical search problems with efficient verification…
?
Complexity of Uhlmann transformations
What about upper bounds on their complexity?
Implementing �Uhlmann transformations
Breaking commitment �schemes
Something funny is going on… EXP could mean multiple things.
EXP
?
Complexity of Uhlmann transformations
What about upper bounds on their complexity?
Implementing �Uhlmann transformations
Breaking commitment �schemes
Fact: Uhlmann transformations can be implemented by a quantum computer in exponential time.
EXP, as in actually �having exponential time
Complexity of Uhlmann transformations
What about upper bounds on their complexity?
Implementing �Uhlmann transformations
Breaking commitment �schemes
Can Uhlmann transformations be efficiently implemented�with oracle access to an EXP-complete decision problem?
EXP, the class of decision �problems solvable by exponential-time Turing machines.
?
Complexity of Uhlmann transformations
What about upper bounds on their complexity?
Implementing �Uhlmann transformations
Breaking commitment �schemes
Can Uhlmann transformations be efficiently implemented�with oracle access to the Halting problem?
Halting Problem
?!
Unitary Synthesis Question
Unitary Synthesis Question
Unitary Synthesis Question
Unitary Synthesis Question
Quantum in, quantum out is different
No-cloning theorem, fragility of quantum information makes quantum input/quantum output problems fundamentally different from classical computation tasks.
Other evidence
No search-to-decision reductions for QMA (“quantum NP”)
Even if P = NP, computationally-secure quantum cryptography can still exist.
[Kretschmer ‘21], [Kretschmer, Qian, Sinha, Tal ‘23]
[Irani, Rao, Natarajan, Nirkhe, Yuen ‘21]
Summary so far
In the Quantum Age, there are interesting computational problems with quantum inputs and quantum outputs.
Traditional complexity theory of decision problems does not seem to be the right framework to reason about quantum cryptography.
Lack of search-to-decision, quantum cryptography in Algorithmica, and the Unitary Synthesis Question suggest we need a �“fully quantum” complexity theory for “fully quantum” computational problems.
Goals of a new complexity theory
Next: an illustration of these goals
Unitary Complexity ��and the��Uhlmann Transformation Problem
John Bostanci
Columbia
Yuval Efron
Columbia
Alexander Poremba
MIT
Tony Metger
ETH
Luowen Qian
Boston University
Joint work with:
Let’s go on safari…
Unscrambling the Hawking radiation of a black hole
Quantum state compression
Decoding noisy quantum channels
Breaking quantum cryptography
Optimal prover �strategies in a quantum�interactive proof
Uhlmann Transformations
Unitary synthesis problems
Quantum Model of Computation
Unitary synthesis problems
Quantum Model of Computation
Unitary complexity theory
A unitary complexity class is a collection of unitary synthesis problems.
unitaryBQP: unitary synthesis problems implementable by polynomial-time algorithms.
unitaryPSPACE: unitary synthesis problems implementable by polynomial-space algorithms.
Reductions
Polynomial-time query algorithm
Uhlmann Transformation Problem
An example of a unitary synthesis problem.
(
,
)
A
B
A
B
specifies
How hard are Uhlmann Transformations?
Theorem* [BEMPQY ‘23]: UHLMANN is complete for unitarySZK, a unitary complexity analogue of statistical zero knowledge.
Is UHLMANN a complete problem for a natural complexity class?
Quantum commitments
Lo, Chau/Mayers: task of breaking quantum commitments polynomial-time reduces to UHLMANN.
Converse?
Idea: Hard instances of UHLMANN yield “weak quantum commitments” that can be amplified to “strong” commitments using the quantum parallel repetition theorem of [BQSY ‘23].
Decoding noisy quantum channels
Noisy Quantum Channel
Decoder
Encoder
Often a random code
Often unknown complexity
Fundamental goal in quantum Shannon theory: given a noisy quantum channel, find encoding/decoding algorithms that maximize the information recovered.
Source
Dest
Decoding noisy quantum channels
Noisy Quantum Channel
Decoder
Encoder
Often a random code
Often unknown complexity
Fundamental goal in quantum Shannon theory: given a noisy quantum channel, find encoding/decoding algorithms that maximize the information recovered.
Source
Dest
Decoding decodable quantum channels
Decodable
Channel
Decoder
Source
Dest
A channel that is �promised to have a decoder.
What is the complexity?
An algorithmic version of the problem: given circuit description of a decodable channel, implement a decoder that can recover the source with high fidelity.
Decoding decodable quantum channels
Decodable
Channel
Decoder
Source
Dest
A channel that is �promised to have a decoder.
What is the complexity?
The black hole information paradox
Quantum physics: all physical processes are reversible
General relativity: information thrown into a black hole is lost forever
Stephen Hawking: black holes evaporate due to radiation
Black hole
After 1060 years
Cloud of Hawking radiation
Maybe all the
information is in here?
Over the years, physicists have tried to resolve the paradox in different ways.
The black hole information paradox
The latest wrinkle: even if the information is preserved in the Hawking radiation, someone could potentially decode the information, jump into the black hole, and suddenly find two copies of the same quantum state.
In 2013, Harlow and Hayden proposed a complexity-theoretic way out: decoding the Hawking radiation can’t be done in polynomial time!
See also “Black-Hole Radiation Decoding is Quantum Cryptography” by Brakerski (2022).
Succinct Uhlmann
Theorem*: SUCCINCT-UHLMANN is complete for unitaryPSPACE.
Theorem*: SUCCINCT-UHLMANN is complete for unitaryQIP.
Corollary*: unitaryQIP = unitaryPSPACE.
Complexity of quantum cryptography
The security of quantum commitments is equivalent to hardness of UHLMANN.
But there are many other quantum crypto primitives: quantum money, copy-protection, unclonable encryption, certified deletion,… What is the complexity of breaking them in general?
Theorem*: A falsifiable quantum cryptographic assumption is either unconditionally secure, or can be efficiently broken in unitaryPSPACE.
A falsifiable crypto assumption is one that can be efficiently refuted via an interactive game.
Summary and�Future Directions
A framework for unitary complexity theory
avgUnitaryPSPACE = avgUnitaryQIP
avgUnitarySZK
avgUnitaryBQP
SuccinctUhlmann
Uhlmann
Hamiltonian Evolution
Decodable Channels
Breaking Commitments
The unitary complexity�landscape so far….
Unscrambling�Hawking Radiation
Fast-Forwarding Hamiltonian Evolution
We have a much better�understanding of the average-case�versions of these classes…
Interference
Detection
Compression
A zoo of “fully quantum” problems
Quantum Info Theory:
Coding over noisy channels
Entanglement distillation
State compression
State redistribution
Hypothesis testing
State/process tomography
…
Quantum Cryptography �(breaking security of):
Quantum money
Commitment schemes
Pseudorandom states
EFI pairs
One-way state generators
Quantum copy-protection
…
Physics:
Preparing ground states
Hamiltonian time evolution
Decoding Hawking radiation
Interference detection
Metrology
…
Quantum algorithms:
QSVT
Identifying coset states
Unitary property testing
…
Many directions to explore
Thank You For Listening!