Demonstration of algorithmic quantum speedup

Abstract

Quantum algorithms theoretically outperform classical algorithms in solving problems of increasing size, but computational errors must be kept to a minimum to realize this potential. Despite the development of increasingly capable quantum computers (QCs), an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant, noisy intermediate-scale quantum (NISQ) devices has remained elusive. Here, we unequivocally demonstrate such a speedup, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, utilizing two different 27-qubit IBM Quantum (IBMQ) superconducting processors. The speedup is observed on only one of the two QCs (ibmq_montreal) when the quantum computation is protected by dynamical decoupling (DD) -- a carefully designed sequence of pulses applied to the QC that suppresses its interaction with the environment, but not without DD. In contrast to recent quantum supremacy demonstrations, the quantum speedup reported here does not rely on any additional assumptions or complexity-theoretic conjectures and solves a bona fide computational problem, in the setting of a game with an oracle and a verifier.

12 pages, 6 main figures + 5 supplementary figures, 1 table

References in corpus (15)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Strong quantum computational advantage using a superconducting quantum processor
• Exponential algorithmic speedup by quantum walk
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Dynamically Error-Corrected Gates for Universal Quantum Computation
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Experimental quantum speed-up in reinforcement learning agents
• High fidelity quantum gates via dynamical decoupling
• Arbitrarily Accurate Pulse Sequences for Robust Dynamical Decoupling
• ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical Decoupling
• Rigorous Bounds on the Performance of a Hybrid Dynamical Decoupling-Quantum Computing Scheme
• Experimental quantum advantage with quantum coupon collector
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Optimally Stopped Optimization

Cited by in corpus (28)

• Machine Learning for Practical Quantum Error Mitigation
• Quantum Fourier Transform using Dynamic Circuits
• Simulating Chemistry on Bosonic Quantum Devices
• Adaptive variational simulation for open quantum systems
• Modeling low- and high-frequency noise in transmon qubits with resource-efficient measurement
• Benchmarking quantum gates and circuits
• Comparative study of quantum error correction strategies for the heavy-hexagonal lattice
• Dynamically Generated Decoherence-Free Subspaces and Subsystems on Superconducting Qubits
• Stabilizing two-qubit entanglement with dynamically decoupled active feedback
• Probing Quantum Telecloning on Superconducting Quantum Processors
• Pulse shape effects in qubit dynamics demonstrated on an IBM quantum computer
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Framework for Learning and Control in the Classical and Quantum Domains
• Resource-efficient context-aware dynamical decoupling embedding for arbitrary large-scale quantum algorithms
• Empirical learning of dynamical decoupling on quantum processors
• Limitations to Dynamical Error Suppression and Gate-Error Virtualization from Temporally Correlated Nonclassical Noise
• Enhancing qubit readout with Bayesian Learning
• Efficient Chromatic-Number-Based Multi-Qubit Decoherence and Crosstalk Suppression
• Virtual Z gates and symmetric gate compilation
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Benchmarking the performance of a high-Q cavity qudit using random unitaries
• Dynamics of qudit gates and effects of spectator modes on optimal control pulses
• Demonstration of High-Fidelity Entangled Logical Qubits using Transmons
• Sparse Non-Markovian Noise Modeling of Transmon-Based Multi-Qubit Operations
• Comparing Algorithms for Loading Classical Datasets into Quantum Memory
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• Computable and noncomputable in the quantum domain: statements and conjectures