Universal Variational Quantum Computation

Abstract

Variational quantum algorithms dominate contemporary gate-based quantum enhanced optimisation, eigenvalue estimation and machine learning. Here we establish the quantum computational universality of variational quantum computation by developing two objective functions which minimise to prepare outputs of arbitrary quantum circuits. The fleeting resource of variational quantum computation is the number of expected values which must be iteratively minimised using classical-to-quantum outer loop optimisation. An efficient solution to this optimisation problem is given by the quantum circuit being simulated itself. The first construction is efficient in the number of expected values for $n$-qubit circuits containing $\mathcal{O}(poly\ln n)$ non-Clifford gates -- the number of expected values has no dependence on Clifford gates appearing in the simulated circuit. The second approach yields $\mathcal{O}(L^2)$ expected values while introducing not more than $\mathcal{O}(\ln L)$ slack qubits, for a quantum circuit partitioned into $L$ gates. Hence, the utilitarian variational quantum programming procedure -- based on the classical evaluation of objective functions and iterated feedback -- is in principle as powerful as any other model of quantum computation. This result elevates the formal standing of the variational approach while establishing a new universal model of quantum computation.

12 pages, RevTeX

References in corpus (13)

• A Quantum Approximate Optimization Algorithm
• Parameterized quantum circuits as machine learning models
• Universal computation by quantum walk
• Variational quantum algorithms for nonlinear problems
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Universal resources for measurement-based quantum computation
• Variational Quantum Linear Solver
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Reachability Deficits in Quantum Approximate Optimization
• On the Universality of the Quantum Approximate Optimization Algorithm
• Quantum approximate optimization is computationally universal
• Machine Learning Phase Transitions with a Quantum Processor
• Certified variational quantum algorithms for eigenstate preparation

Cited by in corpus (45)

• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Variational algorithms for linear algebra
• Quantum Machine Learning: from physics to software engineering
• Abrupt Transitions in Variational Quantum Circuit Training
• Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
• Exponential data encoding for quantum supervised learning
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Variational Simulation of Schwinger's Hamiltonian with Polarisation Qubits
• Networked Quantum Services
• The Unified Effect of Data Encoding, Ansatz Expressibility and Entanglement on the Trainability of HQNNs
• Scalable Quantum Simulations of Scattering in Scalar Field Theory on 120 Qubits
• Mitigating errors by quantum verification and post-selection
• Variational Quantum Cloning: Improving Practicality for Quantum Cryptanalysis
• Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets
• Quantum-machine-learning channel discrimination
• Mitigated barren plateaus in the time-nonlocal optimization of analog quantum-algorithm protocols
• Numerical hardware-efficient variational quantum simulation of a soliton solution
• Partitioning Quantum Chemistry Simulations with Clifford Circuits
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Progress towards analytically optimal angles in quantum approximate optimisation
• Characterization of variational quantum algorithms using free fermions
• Virtual distillation with noise dilution
• Qsun: an open-source platform towards practical quantum machine learning applications
• SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture
• Variational quantum computing for quantum simulation: principles, implementations, and challenges
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Quantum Neural Networks: Concepts, Applications, and Challenges
• Towards solving the BCS Hamiltonian gap in Near-Term Quantum Computers
• Optimized numerical gradient and Hessian estimation for variational quantum algorithms
• Multidimensional Quantum Generative Modeling by Quantum Hartley Transform
• A Critical and Moving-Forward View on Quantum Image Processing
• Variational quantum cloning machine on an integrated photonic interferometer
• A Universal Quantum Computer From Relativistic Motion
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Freedom of mixer rotation-axis improves performance in the quantum approximate optimization algorithm
• Role of overparametrization in quantum approximate optimization
• Optical Quantum Computing
• Zero-Noise Extrapolation via Cyclic Permutations of Quantum Circuit Layouts
• Trainability issues in quantum policy gradients
• Ancillary entangling Floquet kicks for accelerating quantum algorithms
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks