Challenges of variational quantum optimization with measurement shot noise
arXiv:2308.00044 · doi:10.1103/PhysRevA.109.032408
Abstract
Quantum enhanced optimization of classical cost functions is a central theme of quantum computing due to its high potential value in science and technology. The variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) are popular variational approaches that are considered the most viable solutions in the noisy-intermediate scale quantum (NISQ) era. Here, we study the scaling of the quantum resources, defined as the required number of circuit repetitions, to reach a fixed success probability as the problem size increases, focusing on the role played by measurement shot noise, which is unavoidable in realistic implementations. Simple and reproducible problem instances are addressed, namely, the ferromagnetic and disordered Ising chains. Our results show that: (i) VQE with the standard heuristic ansatz scales comparably to direct brute-force search when energy-based optimizers are employed. The performance improves at most quadratically using a gradient-based optimizer. (ii) When the parameters are optimized from random guesses, also the scaling of QAOA implies problematically long absolute runtimes for large problem sizes. (iii) QAOA becomes practical when supplemented with a physically-inspired initialization of the parameters. Our results suggest that hybrid quantum-classical algorithms should possibly avoid a brute force classical outer loop, but focus on smart parameters initialization.
arXiv comment15 pages, 11 figures
References in corpus (47)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Quantum Circuit Learning
- Evaluating analytic gradients on quantum hardware
- Quantum annealing with more than one hundred qubits
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Towards Practical Quantum Variational Algorithms
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Connecting ansatz expressibility to gradient magnitudes and barren plateaus
- Defining and detecting quantum speedup
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Warm-starting quantum optimization
- What is the Computational Value of Finite Range Tunneling?
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Improving Variational Quantum Optimization using CVaR
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Resource-Efficient Quantum Algorithm for Protein Folding
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Optimized simulated annealing for Ising spin glasses
- Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
- Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
- Benchmarking the Quantum Approximate Optimization Algorithm
- Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
- Parameter Concentration in Quantum Approximate Optimization
- Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
- A Threshold for Quantum Advantage in Derivative Pricing
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
- Quantum-enhanced Markov chain Monte Carlo
- Variational Quantum Singular Value Decomposition
- Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
- Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
- Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
- Quantum speedup of branch-and-bound algorithms
- Quantum variational optimization: The role of entanglement and problem hardness
- Finding spin-glass ground states using quantum walks
- To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
- Quantum computing for chemistry and physics applications from a Monte Carlo perspective
- Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
- An evolving objective function for improved variational quantum optimisation
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
- Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
Cited by in corpus (19)
- Quantum computing for chemistry and physics applications from a Monte Carlo perspective
- Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
- Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
- Variational Quantum Multi-Objective Optimization
- Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
- A Quantum Annealing Protocol to Solve the Nuclear Shell Model
- From quantum-enhanced to quantum-inspired Monte Carlo
- Quantum computing for genomics: conceptual challenges and practical perspectives
- Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
- Survey on Computational Applications of Tensor Network Simulations
- Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
- End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
- Toward scalable quantum computations of atomic nuclei
- Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
- Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems
- Challenges and opportunities in the supervised learning of quantum circuit outputs
- Error and Resource Estimates of Variational Quantum Algorithms for Solving Differential Equations Based on Runge-Kutta Methods
- Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods
- Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz