Resilience-Runtime Tradeoff Relations for Quantum Algorithms

Abstract

A leading approach to algorithm design aims to minimize the number of operations in an algorithm's compilation. One intuitively expects that reducing the number of operations may decrease the chance of errors. This paradigm is particularly prevalent in quantum computing, where gates are hard to implement and noise rapidly decreases a quantum computer's potential to outperform classical computers. Here, we find that minimizing the number of operations in a quantum algorithm can be counterproductive, leading to a noise sensitivity that induces errors when running the algorithm in non-ideal conditions. To show this, we develop a framework to characterize the resilience of an algorithm to perturbative noises (including coherent errors, dephasing, and depolarizing noise). Some compilations of an algorithm can be resilient against certain noise sources while being unstable against other noises. We condense these results into a tradeoff relation between an algorithm's number of operations and its noise resilience. We also show how this framework can be leveraged to identify compilations of an algorithm that are better suited to withstand certain noises.

References in corpus (57)

• Quantum Computing
• Variational Quantum Algorithms
• Improved Simulation of Stabilizer Circuits
• NMR Techniques for Quantum Control and Computation
• Logical quantum processor based on reconfigurable atom arrays
• Quantum algorithms: an overview
• Quantum algorithms for quantum chemistry and quantum materials science
• Quantum Fisher information matrix and multiparameter estimation
• Quantum Annealing and Analog Quantum Computation
• Fast optimal frictionless atom cooling in harmonic traps
• On the role of entanglement in quantum computational speed-up
• Distance measures to compare real and ideal quantum processes
• Efficient variational quantum simulator incorporating active error minimisation
• Quantum Error Mitigation
• Quantum Computation as Geometry
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Shortcuts to adiabaticity by counter-diabatic driving
• Real-time quantum error correction beyond break-even
• Quantum Error Correction: An Introductory Guide
• Geometry and non-adiabatic response in quantum and classical systems
• The Second Law of Quantum Complexity
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• The XZZX Surface Code
• Generalized Geometric Quantum Speed Limits
• Detecting crosstalk errors in quantum information processors
• Noise Resilience of Variational Quantum Compiling
• Quantum Simulation of Generic Many-Body Open System Dynamics Using Classical Noise
• Linear growth of quantum circuit complexity
• The methodology of resonant equiangular composite quantum gates
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Quantum annealing with antiferromagnetic fluctuations
• Correcting coherent errors with surface codes
• Machine learning of noise-resilient quantum circuits
• Robustness of composite pulses to time-dependent control noise
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Evaluating the noise resilience of variational quantum algorithms
• Realistic clocks, universal decoherence and the black hole information paradox
• Use of composite rotations to correct systematic errors in NMR quantum computation
• Accuracy vs run time in adiabatic quantum search
• Universal cost bound of quantum error mitigation based on quantum estimation theory
• Robust quantum compilation and circuit optimisation via energy minimisation
• Optimizing quantum gates towards the scale of logical qubits
• Robust resource-efficient quantum variational ansatz through evolutionary algorithm
• Optimal Provable Robustness of Quantum Classification via Quantum Hypothesis Testing
• Demonstration of logical qubits and repeated error correction with better-than-physical error rates
• Quantum evolution according to real clocks
• Universally Robust Quantum Control
• Measurement noise susceptibility in quantum estimation
• The Impact of Imperfect Timekeeping on Quantum Control
• Robustness of quantum algorithms against coherent control errors
• Triply efficient shadow tomography
• Statistically Characterising Robustness and Fidelity of Quantum Controls and Quantum Control Algorithms
• Hardware-Conscious Optimization of the Quantum Toffoli Gate
• Fragile states are better for quantum metrology
• Quantum circuit debugging and sensitivity analysis via local inversions
• Speed-Accuracy Trade-Off Relations in Quantum Measurements and Computations