We show that the variational approach to quantum enhanced algorithms admits a universal model of quantum computation [1].

Variational quantum algorithms dominate contemporary gate-based quantum enhanced optimization [2], eigenvalue estimation [3] and machine learning [4]. Here we establish the quantum computational universality of variational quantum computation by developing two constructions which prepare states with high 2-norm overlap with the outputs of quantum circuits. The fleeting resource is the number of expected values which must be iteratively minimized using a classical-to-quantum feedback loop. The first approach is efficient in the number of expected values for n-qubit circuits containingO(polylnn) non-Clifford gates—the number of expected values has no dependence on Clifford gates appearing in the simulated circuit. The second approach adapts the Feynman-Kitaev clock construction yielding ∼ 4·n+9·(T +1) expected values while introducing not more than T slack qubits, for a quantum circuit partitioned into T Hermitian blocks (gates). The variational model is hence universal and necessitates (i) state-preparation by a control sequence followed by (ii) measurements in one basis and (iii) gradient-free or gradient-based minimization of a polynomially bounded number of expected values.

Discussion

An interesting feature of the model of universal variational quantum computation is how many-body Hamiltonian terms are realized as part of the measurement process. This is in contrast with leading alternative models of universal quantum computation.

In the gate model, many-body interactions are simulated by sequences of two-body gates, where Hamiltonians are emulated using so called Trotter approximations, which can result in painfully long gate sequences. The adiabatic model suffers from the large unrealistic gaps found when applying perturbative gadgets to approximate many-body interactions with two-body interactions [6]. The variational model of universal quantum computation does not suffer from either the Trotter overhead blowup nor does it require perturbative methods. Moreover the coefficients weighting many-body terms need not be implemented into the hardware directly; this weight is compensated for in the classical-iteration process which in turns controls the quantum state being produced.

As the presented model is inherently agnostic to how the states are prepared, this enables experimentalists to now vary the accessible control parameters to minimize an external and iteratively calculated objective function. Though the absolute limitations of this approach in the absence of error correction are not known, a realizable method of error suppression could get us closer to implementation of the traditional text-book quantum algorithms such as Shor’s factorization algorithm.

Dr. Jacob Biamonte is an American theoretical physicist, quantum computer scientist. He is As- sociate Professor and the Lead of Deep Quantum Labs at Skolkovo Institute of Science and Technol- ogy. Biamonte has made several contributions to the theory and implementation of quantum computers.

Biamonte was employed as one of the world’s first quantum software pro- grammers at D-Wave Systems Inc. in Vancouver B.C., Canada. From this work, he published several celebrated proofs establishing the computational uni- versality of specific quantum many-body ground states used in adiabatic quantum computing. He played a central role in developing aspects of con- temporary quantum computing theory, including research recognized as pi- oneering the emerging field that unites quantum information with complex network theory and machine learning.

Biamonte earned an award winning Doctorate at the University of Oxford. His collective research was recognized in 2013 with the Shapiro Award in Math- ematical Physics.

He has advised both government agencies and industry and lead several suc- cessful interdisciplinary research teams and projects, comprised of students and research staff with backgrounds spanning physics, mathematics and computer science. He supervised several extraordinarily talented postdocs, two of which are now Assistant Professors.

Prof. Biamonte serves on the editorial boards of several journals including NJP, he is an invited member of the Foundational Questions Institute and 2018 USERN Medal Laureate.

He has authored several celebrated works on the theory and implementation of quantum information processing, including research recognized as pio- neering the emerging field that unites quantum information with complex network theory and machine learning.

Integrative Data Science Initiative Purdue Quantum Science Engineering Institute, The Chemistry, Physics, and Computer Science Departments at Purdue University Electrical and Computer Engineering at Purdue, Discovery Park, Entanglement Institute

1. Biamonte Jacob. Universal Variational Quantum Computation. arXiv e-prints, arXiv:1903.04500, March 2019.
2. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimiza- tion Algorithm. arXiv e-prints, arXiv:1411.4028, November 2014.
3. A. Peruzzo, J. McClean, P. Shad- bolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien. A vari- ational eigenvalue solver on a photonic quantum processor. Nature Communi- cations, 5:4213, July 2014.
4. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum ma- chine learning. Nature, 549:195–202, September 2017.
5. Seth Lloyd. Quantum approximate optimization is com- putationally universal. arXiv e-prints, page arXiv:1812.11075, December 2018.
6. Jacob D. Biamonte and Peter J. Love. Realizable Hamiltonians for universal adiabatic quantum computers. Physical Review A, 78:012352, July 2008.
7. A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi.Classical and Quantum Computation. American Mathematical Society, Boston, MA, USA, 2002.

Researchers should cite this work as follows:

• Jacob Biamonte (2019), "Universal Variational Quantum Computation," https://nanohub.org/resources/31559.

  BibTex | EndNote

1. algorithms
2. machine learning
3. many body problem
4. quantum computing
5. quantum science and information