A Complexity Theory�for the Quantum Age?

​

Henry Yuen

Columbia

Image credit: Dall-E

What is the Quantum Age?

What my mom thinks

What my experimentalist friends think

What I think

Exponential speedups!

Convincing

quantum advantage

Public-Key Quantum money

Quantum PCP

A zoo of “fully quantum” problems

Quantum Information 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

Preparing/identifying coset states

Unitary property testing

…

​

​

​

A zoo of “fully quantum” problems

Quantum Information 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

Preparing/identifying coset states

Unitary property testing

…

​

​

​

• Solvable in polynomial time?

​

• Reductions between them?

​

• Complete for a complexity class?

​

• Cryptography from their hardness?

​

• …

Classical input

Quantum complexity theory, today:

Models of quantum computation solving problems with classical inputs/outputs

Classical output

Quantum�Computation

We can compare these problems on �classical vs. quantum computers.

Quantum complexity theory, today:

Models of quantum computation solving problems with classical inputs/outputs

Limits of “traditional” complexity theory

• Traditional complexity theory (P, NP, BQP, QMA, decision languages, classical inputs/output problems) appears ill-suited to reason about quantum input/quantum output tasks.

​

• Reason #1: Types don’t match: Nonsensical to say unscrambling black hole radiation is NP-complete (for example).

​

• Reason #2: It’s just different.
• Evidence that search-to-decision reductions don’t hold [IRNNY ‘21].
• Proving results like P = NP may not imply anything about the complexity of quantum input/quantum output tasks (Unitary Synthesis Conjecture).

​

​

​

​

​

​

Fundamental differences

Unitary Synthesis Question

Conjecture: not always possible.

Gold Star Question: prove/disprove Unitary Synthesis Conjecture.

Goals of a new complexity theory:

• Identify natural quantum tasks from the sciences.
• condensed matter physics, high energy physics, chemistry, computer science, cryptography, optimization, experimental physics,…
• Show reductions between them
• Classify them according to computational resources needed
• Identify complete problems
• Prove separations

​

This talk: an illustration of these goals.

�Uhlmann Transformation Problem

The

John Bostanci

Columbia

Yuval Efron

Columbia

Tony Metger

ETH

Luowen Qian

Boston University

Joint work with:

Uhlmann’s Theorem

Uhlmann’s Theorem

Uhlmann Transformation Problem

The Uhlmann Transformation Problem is a unitary synthesis problem, where the goal is to apply an implicitly-specified unitary transformation to a given quantum state.

How hard are Uhlmann Transformations?

How hard are Uhlmann Transformations?

Converse? If one-way functions are invertible in polynomial time, can Uhlmann Transformations be synthesized in polynomial time?

This is an open question. It is unclear whether oracle for any classical decision language is sufficient for efficiently solving Uhlmann Transformation problem.

​

This is another instance of the Unitary Synthesis Question.

Unitary synthesis problems

Need a new framework to think about unitary synthesis problems!

​

No-cloning theorem makes unitary synthesis problems fundamentally different from classical computation tasks.

​

• Since the algorithm cannot know a classical description of input, it cannot know classical description of output.

​

• Thus classical oracles don’t appear to be helpful for unitary synthesis.

Unitary complexity theory

Unitary complexity theory

​

Example: unitaryBQP is the set of polynomial-time implementable unitary synthesis problems.

​

Example: unitaryPSPACE is the set of polynomial-space implementable unitary synthesis problems.

How hard are Uhlmann Transformations?

Theorem* [BEMPQY ‘23]: UHLMANN is complete for unitarySZK, a unitary complexity analogue of statistical zero knowledge.

Centrality of UHLMANN

UHLMANN

Breaking quantum cryptography

Decoding quantum channels

Unscrambling Hawking radiation

State compression

Cloning one-way states

Interference detection*

Centrality of UHLMANN

UHLMANN

Breaking quantum cryptography

Decoding quantum channels

Unscrambling Hawking radiation

State compression

Cloning one-way states

Interference detection*

UHLMANN�and Quantum Cryptography

Commitment schemes

Protocol between two mistrustful parties (committer, receiver). �Cryptographic equivalent of putting a message in sealed envelope that is opened later.

Committer

Receiver

…

Commitment schemes

Protocol between two mistrustful parties (committer, receiver). �Cryptographic equivalent of putting a message in sealed envelope that is opened later.

Committer

Receiver

…

Quantum bit commitments

Theorem [Lo, Chau ’97]: Unconditionally-secure protocols for bit commitments don’t exist, even if the protocol uses quantum messages.

Quantum bit commitments

Quantum bit commitments

Theorem [Bostanci, Spooner, Qian, Y. ‘23]: weak computational binding property can be boosted to strong binding property.

* technically unitaryBQP should be actually avgUnitaryBQP/poly, and we need to additionally assume that hard instances of UHLMANN can be generated efficiently.

Other results

Theorem [BEMPQY ‘23]: Cloning the outputs of a natural class of one-way state generators can be efficiently reduced to a variant of UHLMANN.

This implies a complexity upper bound on breaking a natural class of quantum money schemes.

Other results

Theorem [BEMPQY ‘23]: Cloning the outputs of a natural class of one-way state generators can be efficiently reduced to a variant of UHLMANN.

Theorem [BEMPQY ‘23]: Breaking any falsifiable quantum cryptographic assumption efficiently reduces to SuccinctUHLMANN.

This implies a complexity upper bound on breaking a natural class of quantum money schemes.

SuccinctUHLMANN is variant of UHLMANN where the two states are described succinctly. It is complete for unitaryPSPACE.

Is the hardness of UHLMANN a �minimal assumption in quantum cryptography?

UHLMANN�and Quantum Shannon Theory

Quantum Shannon Theory

• Quantum Shannon Theory: study of quantification, compression and transmission of quantum information.

​

• Fundamental problem in Quantum Shannon theory: �Understand optimal rates of communication over noisy quantum channels.

​

• Quantum Shannon Theory has a complex landscape of different capacities and models of communication.

​

• A computational twist: what is the complexity of achieving optimal communication rates?

Decodable Channel Problem

Maximally entangled�state

Decodable Channel Problem

Decodable Channel Problem

Other results

Theorem [BEMPQY ‘23]:

��

Distinguishing

pseudorandom states

from Haar-random

Optimally compressing

quantum states

Gold Star Question: show compression �task is equivalent to UHLMANN.

Other results

Theorem [BEMPQY ‘23]:

��

Distinguishing

pseudorandom states

from Haar-random

Optimally compressing

quantum states

Idea: black holes can be viewed as channels from infalling information to outgoing radiation. Unitarity means these channels are decodable.

Gold Star Question: show compression �task is equivalent to UHLMANN.

Summary and�Future Directions

A framework for unitary complexity theory

• Traditional complexity theory has hard time reasoning about “fully quantum” tasks: preparing ground states, breaking quantum crypto, quantum channel coding.

​

• A framework of unitary synthesis problems and unitary complexity classes seems better suited to study the complexity of “fully quantum” tasks.

​

• Today: Uhlmann Transformation Problem captures the complexity of:
• Breaking quantum commitments
• Decoding noisy channels
• Zero-knowledge unitary synthesis
• Harlow-Hayden black hole radiation decoding task

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

Many directions to explore

• A new complexity theory: Define and study other unitary complexity classes (e.g., unitaryQMA?), and the relationships between each other. Populate them with interesting quantum input/output tasks.

​

• Foundations of quantum crypto: what is complexity of breaking quantum money or other uncloneable quantum primitives? Are there average-case to worst-case reductions? Is there a minimal complexity assumption needed for quantum crypto?

​

• Traditional vs unitary complexity theory: Is UHLMANN in unitaryBQP^PSPACE? What about unitaryBQP^HALT ?

​

Thank You For Listening!