Abstract
One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as “quantum computational supremacy,” referring to the experimental realization of a quantum device that computationally outperforms classical computers. In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation. In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis. The correctness of the final-state preparation in each scheme is fully efficiently certifiable. We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments. This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing. Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.
2 More- Received 8 August 2017
- Revised 20 December 2017
DOI:https://doi.org/10.1103/PhysRevX.8.021010
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
Quantum computing, which relies on the often bizarre and nonintuitive behavior of subatomic particles, offers the potential to solve problems that cannot be handled by even the most powerful traditional supercomputers. As a step toward creating a universal, fault-tolerant quantum computer, researchers are focused on creating simple devices that show a marked speedup compared to their classical cousins. However, it is currently impossible to experimentally demonstrate if such a speedup exists. One route towards achieving these benchmarks is to rigorously prove a speedup for experimentally available, quantum many-body systems and then invoke further advances in computer theory, physics, and numerical studies. Crucially, one must be able to certify that the output of a quantum device is correct, which is a highly nontrivial task. Here, we demonstrate that a certifiable and rigorous quantum speedup is possible for architectures achievable with present technology, even in the presence of reasonable noise levels.
Our scheme requires little local control and is inspired by dynamical quantum simulation experiments in setups that use cold atoms. In these systems, a product state is prepared, evolved under a local translation-invariant Hamiltonian, and measured in a single shot. We devise a scheme on a two-dimensional square lattice that complies with these experimental requirements while at the same time allowing for a rigorous certificate via a simple product measurement on the final state. We prove that sampling from the distribution of measurement outcomes is intractable on a classical computer even up to an experimentally plausible error.
Our work makes it possible, in the near future, to devise a means for demonstrating and certifying a quantum speedup in a realistic experimental architecture.