2017/03/31 by J. Bermejo-Vega, Juan Bermejo-Vega, Dominik Hangleiter +7 · 4 citations
Computer Science · Physics and Astronomy · #Computer science #Parallel computing #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum computer #Quantum many-body systems #Quantum mechanics #Speedup #cond-mat.other #quant-ph
paper · pdf · doi:10.1103/physrevx.8.021010
published as Phys. Rev. X 8, 021010 (2018) · 13+9 pages, 9 figures, emphasized feasibility, added material on the verification step
arxiv created 2017/12/20 · openalex publication_date 2018/04/09 · arxiv updated 2018/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.