- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Complexity-Theoretic Foundations of Quantum Supremacy...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Complexity-Theoretic Foundations of Quantum Supremacy Experiments Aaronson, Scott
Description
Depending on time, I'll discuss some subset of the following results. (1) There exists an oracle relative to which classical and quantum computers can solve the same approximate sampling problems in polynomial time, and yet the polynomial hierarchy is infinite. This means that any "BosonSampling-type theorem" will need to be non-relativizing. (2) Can P be separated from BQP by an efficiently-computable oracle (one in P/poly)? Yes if quantum-resistant one-way functions exist; no if P=PSPACE. The latter builds on recent results in quantum query complexity by myself and Shalev Ben-David. (3) How hard is it to approximately sample the output distribution of a random quantum circuit? One can do it (and even calculate the probabilities) in polynomial space and m^O(n) time, where m is the number of gates and n is the number of qubits. But if that's essentially optimal for estimating probabilities, then approximate sampling also requires exponential time. Joint work with Lijie Chen (Tsinghua University)
Item Metadata
| Title |
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2016-09-08T20:04
|
| Description |
Depending on time, I'll discuss some subset of the following results.
(1) There exists an oracle relative to which classical and quantum
computers can solve the same approximate sampling problems in
polynomial time, and yet the polynomial hierarchy is infinite. This
means that any "BosonSampling-type theorem" will need to be
non-relativizing.
(2) Can P be separated from BQP by an efficiently-computable oracle
(one in P/poly)? Yes if quantum-resistant one-way functions exist; no
if P=PSPACE. The latter builds on recent results in quantum query
complexity by myself and Shalev Ben-David.
(3) How hard is it to approximately sample the output distribution of
a random quantum circuit? One can do it (and even calculate the
probabilities) in polynomial space and m^O(n) time, where m is the
number of gates and n is the number of qubits. But if that's
essentially optimal for estimating probabilities, then approximate
sampling also requires exponential time.
Joint work with Lijie Chen (Tsinghua University)
|
| Extent |
54 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Massachusetts Institute of Technology
|
| Series | |
| Date Available |
2017-03-09
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0343134
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International