When: Monday, August 1, 2022 9:00 am - Wednesday, August 3, 2022 5:00 pm
Where: David Rubenstein Forum at the University of Chicago, 1201 E 60th St, Chicago, IL 60637
Description: We have now arrived at a critical moment on the path towards developing large-scale quantum computers. For the first time, existing quantum experiments are pushing the boundaries of what is possible with a classical computer, and we have recently seen the first claimed experimental demonstrations of quantum advantage.
Besides dispelling any skepticism about the experimental viability of quantum computers, quantum advantage also provides a test of quantum theory in the realm of high complexity. This workshop will bring together quantum computing theorists and experimentalists to discuss the state-of-the-art research on quantum advantage. The focus will be both on understanding these experiments, as well as analyzing the extent to which these initial “proof of principle” demonstrations can provide a foundation for the next generation of quantum experiments that will obtain speedups for practically useful computational problems.
|
Time |
|
| 9:00 – 9:45 AM | Registration and Breakfast |
| 9:45 – 10:00 AM | Opening remarks – Bill Fefferman (University of Chicago) |
| 10:00 – 11:00 AM | Umesh Vazirani (University of California, Berkeley) via Zoom |
| 11:00 AM – 12:00 PM |
Scott Aaronson (University of Texas, Austin) Verifiable Quantum Supremacy: What I Hope Will Be Done |
| 12:00 – 1:30 PM | Lunch at Rubenstein Forum |
| 1:30 – 2:30 PM |
David Gosset (University of Waterloo) Shallow Clifford circuits: quantum advantage and classical simulation |
| 2:30 – 3:30 PM |
Alexey Gorshkov (University of Maryland/NIST) Candidate for a passively-protected quantum memory in two dimensions |
| 3:30 – 4:00 PM | Break |
| 4:00 – 5:00 PM |
Manuel Endres (California Institute of Technology) Probing Quantum Many-Body Dynamics with Tweezer Arrays |
| Time | |
| 9:00 – 9:45 AM | Breakfast |
| 9:45 – 10:00 AM | Perspective from NSF – Almadena Chtchelkanova (National Science Foundation) |
| 10:00 – 11:00 AM |
Chaoyang Lu (University of Science and Technology of China) via Zoom Photonic quantum computational advantage |
| 11:00 – 12:00 PM |
Nicolas Quesada (Polytechnique Montreal) Quantum computational advantage with a programmable photonic processor |
| 12:00 – 1:30 PM | Lunch at Rubenstein Forum |
| 1:30 – 2:30 PM |
Daniel Grier (University of Waterloo) The Complexity of Bipartite Gaussian Boson Sampling |
| 2:30 – 3:30 PM |
Changhun Oh (University of Chicago) Quantum-inspired classical algorithm for molecular vibronic spectra |
| 3:30 – 4:00 PM | Break |
| 4:00 – 5:00 PM |
Benjamin Villalonga (Google) Classical adversaries to the experimental demonstrations of quantum advantage |
| 5:00 – 6:00 PM | Break and Poster session at Rubenstein Forum |
| 6:00 PM | Dinner at Rubenstein Forum |
| Time | |
| 9:00 – 10:00 AM | Breakfast |
| 10:00 – 11:00 AM |
Abhinav Deshpande (California Institute of Technology) Noisy random circuits and implications for hardness |
| 11:00 AM – 12:00 PM |
Dominik Hangleiter (University of Maryland) Verifiable measurement-based quantum random sampling with trapped ions |
| 12:00 – 1:30 PM | Lunch at Rubenstein Forum |
| 1:30 – 2:30 PM |
Alexandru Gheorghiu (ETH Zurich) Proofs of quantumness: overview and challenges for near-term devices |
| 2:30 – 3:30 PM |
Crystal Noel (Duke University) Approaching Quantum Advantage with Trapped Ions |
| 3:30 – 4:00 PM | Break |
| 4:00 – 5:00 PM |
Xun Gao (Harvard University) Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage |
Confirmed speakers include:
- Scott Aaronson, University of Texas at Austin
- Almadena Chtchelkanova, NSF
- Abhinav Deshpade, Caltech
- Manuel Endres, Caltech
- Xun Gao, Harvard University
- Alexandru Gheorghiu, ETH Zürich
- Alexey Gorshkov, University of Maryland/NIST
- David Gosset, University of Waterloo
- Daniel Grier, University of Waterloo
- Dominik Hangleiter, University of Maryland
- Chao-Yang Lu, University of Science and Technology of China
- Crystal Noel, Duke University
- Changhun Oh, University of Chicago
- Nicolas Quesada, Polytechnique Montréal
- Umesh Vazirani, University of California Berkeley
- Benjamin Villalonga, Google
Scott Aaronson, University of Texas at Austin
Title: Verifiable Quantum Supremacy: What I Hope Will Be Done
Description: I'll describe and advocate a research agenda for designing experiments that are (1) feasible on NISQ devices, (2) hard to simulate classically, and (3) easy to verify classically, where right now we only have any two out of the three. This agenda involves understanding the structure of otherwise-random quantum circuits that have been postselected to have the behavior that we want (such as producing verifiable outputs).
Almadena Chtchelkanova, National Science Foundation
Title: Perspective from NSF
Description: From World Quantum Day to the National Quantum Initiative, the National Science Foundation in the United States is playing a major role in the next quantum revolution. NSF funding and our peer review process promotes a culture of discovery and cutting-edge science. We also see new opportunities with partnerships and international cooperation to get more people involved. This is how we can accelerate progress in the multidisciplinary field of Quantum Information Science and Engineering (QISE).
In physical science, computer science, and engineering - fields underpinning quantum technologies – the National Science Foundation is the largest Government sponsor for basic research at Colleges and Universities in the United States. In Quantum Information Science and Engineering in particular, NSF is supporting over 1,200 projects with current awards for quantum computing, quantum networking, and quantum sensing. These QISE awards support 227 institutions in 47 different states, and over 1100 unique Principal Investigators. Approximately 2000 student researchers (breakdown: 1500 graduate students and 500 undergraduates) are getting trained by doing cutting-edge research in QISE supported by NSF. In aggregate, these awards are funded with about $200 Million per year from NSF.
But we still need to understand quantum advantage. The U.S. strategy for QIS emphasizes a science-first approach. We still have a lot of basic research and discovery to do. At the same time, we would like to know, how can quantum computers benefit society? What are the applications, and what is the timeframe for bringing these applications to reality?
Abhinav Deshpande, Caltech
Title: Noisy random circuits and implications for hardness
Description: In this talk, we will discuss some properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the "useless" uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work. arXiv reference: arXiv:2112.00716
Manuel Endres, Caltech
Title: Probing Quantum Many-Body Dynamics with Tweezer Arrays
Description: Atom-by-atom assembly with optical tweezers enables the generation of defect-free atomic arrays with flexible geometric arrangements. Combined with controlled excitation to Rydberg states, this has become a highly versatile platform for quantum computing, simulation, and metrology. I will review these developments with a focus on two valence electron atoms: The rich level structure of such atoms enables novel cooling, control, and read-out schemes, which we have used in demonstrations of record imaging and two-qubit entanglement fidelities for neutral atoms.
Xun Gao, Harvard University
Title: Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Description: In recent experiments, Google and USTC claimed to achieve quantum advantage based on sampling from random quantum circuits. To certify the correctness of the sampling task, they developed a linear cross-entropy benchmark (XEB) and made their claim based on achieving a high value of XEB. The implicit assumption is that XEB approximates the fidelity well and hence could serve as a proxy in practice. However, it turns out that XEB can often deviate from fidelity, so it is crucial to understand how XEB and fidelity are related. I introduce a novel approach to analyze XEB through a mapping of random quantum circuits to a discrete classical statistical-physics models. By analyzing this model by a combination of qualitative analysis, numerical computation, and analytical methods, we show that XEB could drastically overestimates fidelity under certain conditions. Based on this observation, we design a classical spoofing algorithm which achieves comparable XEB values to those obtained in the state-of-the-art experiments by using 1 GPU within 1 second. Furthermore, we show that this algorithm performs better than noisy quantum circuits in the limit of large system size and depth in many cases. These results indicate that XEB on its own is not a good benchmark to certify quantum advantage.
Alexandru Gheorghiu, ETH Zürich
Title: Proofs of quantumness: overview and challenges for near-term devices
Abstract: Recent demonstrations of quantum computational advantage by groups at Google and USTC have highlighted the impressive capabilities of near-term quantum computers. However, these experiments come at the cost of requiring exponential time to check the results. Is it possible to certify quantum advantage efficiently (i.e. in polynomial time)? The answer is yes, and one approach is with protocols known as proofs of quantumness. In this talk, I will give a brief overview of proof of quantumness protocols and then discuss recent work aiming to make these protocols suitable for use with non-fault-tolerant quantum computers. I'll also discuss remaining challenges and open problems.
Alexey Gorshkov, University of Maryland/NIST
Title: Candidate for a passively-protected quantum memory in two dimensions
Abstract: An interesting problem in the field of quantum error correction involves finding a physical system that hosts a "passively-protected quantum memory,'' defined as an encoded qubit coupled to an environment that naturally wants to correct errors. To date, a quantum memory stable against finite-temperature effects is only known in four spatial dimensions or higher. Here, we take a different approach to realize a stable quantum memory by relying on a driven-dissipative environment. We propose a new model which appears to passively correct against both bit-flip and phase-flip errors in two dimensions: A square lattice composed of photonic "cat qubits'' coupled via dissipative terms which tend to fix errors locally. Inspired by the presence of two distinct Z_2-symmetry-broken phases, our scheme relies on Ising-like dissipators to protect against bit flips and on a driven-dissipative photonic environment to protect against phase flips.
David Gosset, University of Waterloo
Title: Shallow Clifford circuits: quantum advantage and classical simulation
Description: Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster --as measured by circuit depth-- than classical computers. In this talk I will discuss the type of quantum advantage that is attained by Clifford circuits as well as improved classical simulation algorithms for the case where the circuit to be simulated has a planar geometry.
Daniel Grier, University of Waterloo
Title: The Complexity of Bipartite Gaussian Boson Sampling
Abstract: In this talk, I will show that under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Our proof relies on a generalization of Scattershot BosonSampling which allows us to program a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. I will wrap up by discussing some of the challenges needed to prove hardness in the regime where the number of modes is linear in the number of photons.
Dominik Hangleiter, University of Maryland
Title: Verifiable measurement-based quantum random sampling with trapped ions
Abstract: Quantum random sampling performed on near-term devices can demonstrate the computational advantage of quantum computing devices and moreover has applications as a device benchmark. However, verifying quantum random sampling remains an outstanding challenge since existing verification tools are not scalable to the quantum advantage regime. In this talk, I will begin discussing what means are available to convince ourselves of the quality of quantum random sampling implementations. I will then argue for a clean framework for verification of quantum random sampling in terms of the fidelity, and show how the verification can be elegantly solved in the measurement-based model of quantum computing. I will then present a verified experimental demonstration of measurement-based quantum random sampling using trapped-ion quantum processors. Experimentally the demonstration uses pairwise addressed entangling gates and recycling of ions to create resource states that are larger than the qubit register.
Chao-yang Lu, University of Science and Technology of China
Title: Photonic quantum computational advantage
Description: The main challenge for scaling up photonic quantum technologies is the lack of perfect quantum light sources. We have pushed the parametric down-conversion to its physical limit and produce two-photon source with simultaneously a collection efficiency of 97% and an indistinguishability of 96% between independent photons. Using a single quantum dot in microcavities, we have produced on-demand single photons with high purity (>99%), near-unity indistinguishability, and high extraction efficiency—all combined in a single device compatibly and simultaneously. Based on the high-performance quantum light sources, we have implemented boson sampling—which is an intermediate model of quantum computing, a strong candidate for demonstrating quantum computational advantage and refuting Extended Church Turing Thesis—with up to 113 photon clicks after a 144-mode interferometer. The photonic quantum computer, Jiuzhang, yields an output state space dimension of 10^43 and a sampling rate that is 10^24 faster using the state-of- the-art simulation strategy on supercomputers.
Crystal Noel, Duke University
Title: Approaching Quantum Advantage with Trapped Ions
Abstract: Achieving "Quantum Advantage" can be interpreted as having some level of "quantumness" in your device, such as in a Bell inequality violation. The phrase has also been used to mean that a quantum computer has performed a task that is otherwise "slow" on a classical computer. Finally, the most intriguing definition refers to the ability of a quantum computer to teach us something new - in other words to advance our scientific knowledge beyond what was previously possible. In this talk, I will address how we tackle each one of these interpretations using a trapped ion quantum computer. I will discuss recent results such as interactive protocols to show quantumness, cross platform verification for near term advantage, and projections of our recent NMR simulations into the quantum advantage era. I will also discuss ideas for the future of achieving quantum advantage and how ions might get us there.
Changhun Oh, University of Chicago
Title: Quantum-inspired classical algorithm for molecular vibronic spectra
Description: Over the last few years, there have been many experimental demonstrations of quantum computational advantages using random circuit sampling and Gaussian boson sampling. On the other hand, there have been many theoretical proposals for practical applications of such tasks. One interesting candidate is the so-called molecular vibronic spectra, which is believed to be hard to compute and might potentially take advantage of a Gaussian boson sampler’s computational power. In this talk, I will talk about a quantum-inspired classical algorithm for molecular vibronic spectra, which allows us to compute the spectra without using a quantum device. It implies that the molecular vibronic spectra problems which can be mapped onto a Gaussian boson sampling experiment do not require a quantum device. I will then discuss a generalization of the task beyond Gaussian boson sampling and the hardness of the related problems. I will finally provide approximate classical algorithms and find certain cases where the algorithms achieve the same accuracy as a quantum simulator.
Nicolas Quesada, Polytechnique Montréal
Title: Quantum computational advantage with a programmable photonic processor
Description: A quantum computer attains computational advantage when outperforming the best classical computers running the best-known algorithms on well-defined tasks. We report quantum computational advantage using Borealis, a photonic processor offering dynamic programmability on all gates implemented. We carry out Gaussian boson sampling (GBS) on 216 squeezed modes entangled with three-dimensional connectivity, using a time-multiplexed and photon-number-resolving architecture. On average, it would take more than 9,000 years for the best available algorithms and supercomputers to produce, using exact methods, a single sample from the programmed distribution, whereas Borealis requires only 36 μs. This runtime advantage is over 50 million times as extreme as that reported from earlier photonic machines. Ours constitutes a very large GBS experiment, registering events with up to 219 photons and a mean photon number of 125. This work is a critical milestone on the path to a practical quantum computer,
Benjamin Villalonga, Google
Title: Classical adversaries to the experimental demonstrations of quantum advantage
Description: Over the last three years, a few landmark experiments have aimed at demonstrating quantum advantage by performing computations thought to be beyond the reach of classical computers. Meanwhile, classical algorithms and their implementations have improved substantially at performing these same computational tasks, playing the role of classical adversaries to quantum advantage claims. In this talk, I will give a non-exhaustive review of the recent developments on classical adversaries to the experimental random circuit sampling and Gaussian boson sampling quantum advantage claims. Throughout the talk, I will point out key differences between these two sampling tasks that have important implications from the classical adversary point of view.
Thank you to our sponsors:
The Workshop on Quantum Advantage and Next Steps Program Committee is comprised of:
- Chair: Bill Fefferman, University of Chicago
- Scott Aaronson, University of Texas at Austin
- Hannes Bernien, University of Chicago
- Adam Bouland, Stanford University
- Abhinav Deshpande, Caltech
- Umesh Vazirani, University of California Berkeley
We expect everyone in our community to follow these guidelines when interacting with others both inside and outside of our community. Our goal is to keep ours a positive, inclusive, successful, and growing community.
This workshop is open to the public:
In addition to attending, CQE trainees are invited to present a poster on the second day of the workshop (space permitting). Submit your poster information here.