Skip to content

Variational quantum algorithms

Rough overview (in words)

The so-called Noisy Intermediate-Scale Quantum (NISQ) era is a term used to describe the regime in which the best quantum processors have fifty to a few hundred noisy qubits [1]. In this regime, one does not have enough qubits or low enough error rates to carry out fault-tolerant quantum computation, and so one is constrained to run low-depth quantum circuits. Under these constraints, structured quantum algorithms with prescribed circuits and provable guarantees are unknown. In light of this, variational quantum algorithms (VQAs) have been proposed. We remark that, despite this original setting, it would also be possible to run VQAs on fault-tolerant devices. Whilst many VQAs have been proposed for a wide range of applications, they all share the same core primitive which we describe below.

The main idea is to encode the target problem into an optimization task of minimizing the expectation value of some parametrized quantum circuit, or a function thereof. In each optimization step, a quantum computer is used to evaluate expectation values at chosen parameter values, which are read by a classical optimizer that updates the parameters for the next step. The motivation for this framework is to offload some of the computational complexity onto the classical optimization algorithm, with an aim for the quantum subroutines to perform classically intractable calculations.

Rough overview (in math)

Given some parametrized unitary \(U(\boldsymbol{\theta})\) with adjustable parameters \(\boldsymbol{\theta}\), input state \(\rho\), measurement operator \(O\), and function \(f(\cdot)\), one evaluates \(C(\boldsymbol{\theta})=f\left(\operatorname{Tr}\left[O U(\boldsymbol{\theta}) \rho U^{\dagger}(\boldsymbol{\theta})\right] \right)\) on a quantum computer, which is known as a cost function. A classical optimizer is then tasked to solve the problem \(\boldsymbol{\theta}_*=\textrm{argmin}_{\boldsymbol{\theta}}f\left(\operatorname{Tr}[O U(\boldsymbol{\theta}) \rho U^{\dagger}(\boldsymbol{\theta})]\right)\). By careful choice of \(f(\cdot)\), \(\rho\), and \(O\), one can encode a problem of interest such that \(U(\boldsymbol{\theta}_*)\) enables an (approximate) solution to the problem. For instance, the solution could correspond to the projection of the output state \(U(\boldsymbol{\theta}_*)\rho U(\boldsymbol{\theta}_*)^{\dagger}\) to the computational basis, or to the value of \(f(\operatorname{Tr}[O U(\boldsymbol{\theta}_*) \rho U(\boldsymbol{\theta}_*)^{\dagger}])\) itself. In general, one can also construct a more elaborate cost function comprising a sum of observable-dependent functions with different input states and measurement operators.

The parametrized circuit \(U(\boldsymbol{\theta})\) is commonly referred to as the "ansatz circuit." The choice of cost function and ansatz are key components in designing a VQA. Namely, they should ideally satisfy the following properties:

  1. Smaller values of the cost function should correspond to better quality of solution.
  2. The ansatz should be sufficiently expressible to contain a unitary \(U(\boldsymbol{\theta}_*)\) which yields an acceptable solution.
  3. The ansatz should lead to a trainable cost landscape in parameter space, such that a sufficiently good solution can be found efficiently by the classical optimizer.
  4. The cost function should be classically hard to simulate, given the choice of ansatz.

It should be noted that whilst one would expect any VQA to satisfy the first point by design, in general it can be hard to satisfy all of the above requirements simultaneously via theoretical guarantees or even heuristically in practice. These caveats are discussed in more detail below.

Dominant resource cost (gates/qubits)

The gate complexity is wholly dependent on the choice of ansatz. Satisfying properties (2) and (4) may place lower bounds on the required circuit depth. In addition, the connectivity of the device may also significantly affect the depth of the circuit. For instance, compilation of a single generic (multiqubit) gate on hardware with \(1\)D connectivity incurs \(\mathcal{O}\left( n \right)\) circuit depth, where \(n\) is the number of qubits.

Throughout the optimization, the cost function is evaluated at different parameter settings \(\boldsymbol{\theta}\), chosen adaptively based on the outcome of prior evaluations (in the case of gradient-based optimization, one can use the parameter shift rule [2, 3, 4, 5] or finite-difference methods). Each evaluation of the cost function corresponds to approximating an expectation value to some additive error \(\varepsilon\) using finite measurement shots, where \(\varepsilon\) should be chosen to be sufficiently small for accurate optimization over the landscape. Specifically, it should be expected that \(\varepsilon\) is at most \(\smash{\mathcal{O}\left(\sqrt{\operatorname{Var}_{\boldsymbol{\theta}}C(\boldsymbol{\theta})}\right)}\) in order to distinguish different points in the parameter landscape, where \(\operatorname{Var}_{\boldsymbol{\theta}}\) denotes the variance over uniformly distributed parameter settings.

Caveats

The optimization of certain parametrized quantum circuits is known to be subject to the detrimental phenomena of "barren plateaus," in which deviations between different cost values with high probability (or deterministically, depending on the setting) vanish exponentially with increasing number of qubits [6, 7, 8, 9, 10, 11, 12, 13]. This is often characterized by observing that \(\operatorname{Var}_{\boldsymbol{\theta}}C(\boldsymbol{\theta}) = \mathcal{O}\left( 2^{-\beta n} \right)\) for some \(\beta \geq 0\) [14]. This mandates an exponential shot complexity for each evaluation of a cost value in order to reliably navigate the cost landscape. Note that this affects both gradient-based and gradient-free optimization strategies.

If VQAs are run on noisy devices, the effects of noise are known to severely restrict the scope for computation [15, 16, 17, 18, 19]. This effect is amplified on devices with limited hardware connectivity, where one has to use additional circuit depth to compile generic gates [18, 17].

Finally, in general there is a lack of end-to-end theoretical guarantees for variational quantum algorithms. In order to show advantage over classical algorithms, at minimum one has to satisfy all of the properties laid out above. In particular the classical parameter optimization is generally left as a heuristic subroutine. This optimization task is in general NP-hard, and can be burdened by many local minima of poor quality [20, 21]. This leads to a slow optimization process and many cost values may need to be evaluated.

Example use cases

  • Quantum chemistry and condensed matter physics: The ground state and ground state energy of a given Hamiltonian \(H\) can be found by minimizing the cost \(\langle\psi(\boldsymbol{\theta})|H| \psi(\boldsymbol{\theta})\rangle\), where \(\ket{\psi(\boldsymbol{\theta})}=U(\boldsymbol{\theta})\ket{\psi_0}\) for some input state \(\ket{\psi_0}\) [22]. This is known as the Variational Quantum Eigensolver (VQE) algorithm. A widely used ansatz for fermionic Hamiltonians is the Unitary Coupled Cluster (UCC) ansatz [23, 22, 24, 25, 26, 27, 28, 29].
  • Combinatorial optimization: In the Quantum Approximate Optimization Algorithm (QAOA), combinatorial problems on bitstrings can be encoded in the Pauli-\(Z\) basis with Hamiltonian \(H_P\) [30]. By finding the state that minimizes \(\langle\phi(\boldsymbol{\theta})|H_P| \phi(\boldsymbol{\theta})\rangle\), where \(\ket{\phi(\boldsymbol{\theta})} = U(\boldsymbol{\theta})\ket{0}\), the optimal bit-string can be extracted by sampling the optimized state in the computational basis. A widely studied ansatz for this problem is the Quantum Alternating Operator Ansatz (which bears the same acronym as the algorithm), inspired by Trotterized adiabatic evolution [31]. The ansatz takes the form \(U(\boldsymbol{\gamma}, \boldsymbol{\beta})=\prod_{l=1}^{p} e^{-i \beta_{l} H_{M}} e^{-i \gamma_{l} H_{P}}\) where \(H_M\) is a specific "mixing\" Hamiltonian. This ansatz is known to be computationally universal (when \(p\rightarrow \infty\)) for certain classes of Hamiltonians [32, 33]. Moreover, under reasonable complexity-theoretic assumptions, it is known that sampling from the output of the QAOA at \(p=1\) is classically hard [34]. On the other hand, there is evidence that shallow (small \(p\)) QAOA does not perform well [35, 36, 37, 38], leading to intuition that \(p\) may need to grow with problem size to produce better approximate solutions than what can be easily found classically. Alternatively, there is some evidence that an exponential number of samples from shallow QAOA circuits may yield polynomial speedups over classical methods for finding exactly optimal solutions [39, 40], see the page on beyond-quadratic speedups for combinatorial optimization.
  • Linear systems solvers: Given matrix \(A\) and vector \(b\) encoded in a quantum state \(\ket{b}\), the goal is to variationally prepare a quantum state \(\ket{x}\) with amplitudes proportional to elements of the vector \(x=A^{-1}b\) [41, 42, 43]. The strategy employed is to minimize the cost \(\bra{\tilde{x}(\boldsymbol{\theta})}H_L\ket{\tilde{x}(\boldsymbol{\theta})}\), where \(\ket{\tilde{x}(\boldsymbol{\theta})} = U(\boldsymbol{\theta})\ket{0}\) and \(H_L=A^{\dag}(I-|b\rangle\langle b|)A\). These approaches require the assumption that \(A\) has a decomposition into a sum of a small number of efficiently implementable unitaries. Here the absolute value of the cost function bounds the approximation error. A numerical study up to \(30\) qubits showed favourable scaling in the time to solution with respect to the matrix size, condition number and precision [41].
  • Factoring: Variational methods for factoring have been proposed which exploit a mapping between the factoring problem and that of finding the ground state of an Ising Hamiltonian [44]. The authors use the QAOA ansatz and heuristically find that \(p=\mathcal{O}(n)\) rounds of the ansatz can lead to a good solution overlap for small system sizes.
  • Compiling: An interesting near-term application could be to approximate a given unitary \(V\) with native gate sequence \(U(\boldsymbol{\theta})\). One can construct a cost function via the Hilbert-Schmidt test circuit to evaluate \(1-\left|\bra{\Phi}V^*\otimes U(\boldsymbol{\theta})\ket{\Phi}\right|^2=1-\left|\frac{1}{2^{n}}\mathrm{Tr}[V^{\dag}U(\boldsymbol{\theta})]\right|^2\), where \(\ket{\Phi}\) is the maximally entangled state [45].
  • Machine learning: Here one employs a parametrized quantum circuit to construct a hypothesis family. Variational methods have been proposed for both classical and quantum data for classification [46, 2, 47, 48, 49], generative models [50, 51, 52], autoencoders [53, 54, 55] and beyond [56, 57]. Specific ansätze have been proposed in these contexts, sometimes referred to as quantum neural networks, in analogue with their classical counterparts. "Classically inspired\" quantum neural networks have been proposed, such as perceptron-based QNNs [58, 54, 59, 60] and a quantum analogue to the convolutional neural network [49], as well as approaches based on tensor networks [61, 62].

Further reading

  • See [63, 64] for extensive reviews of VQAs, including a summary of different widely studied ansatzes, applications, and challenges.

Bibliography

  1. John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018. arXiv: https://arxiv.org/abs/1801.00862. doi:10.22331/q-2018-08-06-79.

  2. Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, 98(3):032309, 2018. arXiv: https://arxiv.org/abs/1803.00745. URL: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.98.032309, doi:10.1103/PhysRevA.98.032309.

  3. Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Physical Review A, 99(3):032331, 2019. arXiv: https://arxiv.org/abs/1811.11184. URL: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.99.032331, doi:10.1103/PhysRevA.99.032331.

  4. Gavin E Crooks. Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition. arXiv: https://arxiv.org/abs/1905.13311, 2019.

  5. David Wierichs, Josh Izaac, Cody Wang, and Cedric Yen-Yu Lin. General parameter-shift rules for quantum gradients. Quantum, 2022. arXiv: https://arxiv.org/abs/2107.12390. URL: https://quantum-journal.org/papers/q-2022-03-30-677/, doi:https://doi.org/10.22331/q-2022-03-30-677.

  6. Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1):1–6, 2018. arXiv: https://arxiv.org/abs/1803.11173. URL: https://www.nature.com/articles/s41467-018-07090-4, doi:10.1038/s41467-018-07090-4.

  7. M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1):1–12, 2021. arXiv: https://arxiv.org/abs/2001.00550. URL: https://www.nature.com/articles/s41467-021-21728-w, doi:10.1038/s41467-021-21728-w.

  8. Zoë Holmes, Kunal Sharma, M. Cerezo, and Patrick J Coles. Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum, 3:010313, 1 2022. arXiv: https://arxiv.org/abs/2101.02138. URL: https://link.aps.org/doi/10.1103/PRXQuantum.3.010313, doi:10.1103/PRXQuantum.3.010313.

  9. Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe. Entanglement-induced barren plateaus. PRX Quantum, 2(4):040316, 2021. arXiv: https://arxiv.org/abs/2010.15968. URL: https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.2.040316, doi:10.1103/PRXQuantum.2.040316.

  10. Kunal Sharma, M. Cerezo, Lukasz Cincio, and Patrick J Coles. Trainability of dissipative perceptron-based quantum neural networks. Physical Review Letters, 128(18):180505, 2022. arXiv: https://arxiv.org/abs/2005.12458. doi:10.1103/PhysRevLett.128.180505.

  11. Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J Coles, and Marco Cerezo. Diagnosing barren plateaus with tools from quantum optimal control. Quantum, 6:824, 2022. arXiv: https://arxiv.org/abs/2105.14377. doi:https://doi.org/10.22331/q-2022-09-29-824.

  12. Enrico Fontana, Dylan Herman, Shouvanik Chakrabarti, Niraj Kumar, Romina Yalovetzky, Jamie Heredge, Shree Hari Sureshbabu, and Marco Pistoia. The adjoint is all you need: characterizing barren plateaus in quantum ansätze. arXiv: https://arxiv.org/abs/2309.07902, 2023.

  13. Michael Ragone, Bojko N Bakalov, Frédéric Sauvage, Alexander F Kemper, Carlos Ortiz Marrero, Martin Larocca, and M Cerezo. A unified theory of barren plateaus for deep parametrized quantum circuits. arXiv: https://arxiv.org/abs/2309.09342, 2023.

  14. Andrew Arrasmith, Zoë Holmes, Marco Cerezo, and Patrick J Coles. Equivalence of quantum barren plateaus to cost concentration and narrow gorges. Quantum Science and Technology, 7(4):045015, 2022. arXiv: https://arxiv.org/abs/2104.05868. URL: https://iopscience.iop.org/article/10.1088/2058-9565/ac7d06, doi:10.1088/2058-9565/ac7d06.

  15. Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan. Limitations of noisy reversible computation. arXiv: https://arxiv.org/abs/quant-ph/9611028, 1996.

  16. Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim. Quantum refrigerator. arXiv: https://arxiv.org/abs/1301.1995, 2013. URL: https://arxiv.org/abs/1301.1995.

  17. Samson Wang, Enrico Fontana, M. Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum algorithms. Nature Communications, 12(1):1–11, 2021. arXiv: https://arxiv.org/abs/2007.14384. URL: https://www.nature.com/articles/s41467-021-27045-6, doi:10.1038/s41467-021-27045-6.

  18. Daniel Stilck França and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quantum devices. Nature Physics, 17(11):1221–1227, 2021. arXiv: https://arxiv.org/abs/2009.05532. doi:10.1038/s41567-021-01356-3.

  19. Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França. Limitations of variational quantum algorithms: a quantum optimal transport approach. PRX Quantum, 4:010309, 1 2023. arXiv: https://arxiv.org/abs/2204.03455. URL: https://link.aps.org/doi/10.1103/PRXQuantum.4.010309, doi:10.1103/PRXQuantum.4.010309.

  20. Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is np-hard. Physical Review Letters, 127:120502, 9 2021. arXiv: https://arxiv.org/abs/2101.07267. URL: https://link.aps.org/doi/10.1103/PhysRevLett.127.120502, doi:10.1103/PhysRevLett.127.120502.

  21. Eric R Anschuetz and Bobak T Kiani. Quantum variational algorithms are swamped with traps. Nature Communications, 13(1):7760, 2022. arXiv: https://arxiv.org/abs/2205.05786. doi:https://doi.org/10.1038/s41467-022-35364-5.

  22. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 2014. arXiv: https://arxiv.org/abs/1304.3061. doi:10.1038/ncomms5213.

  23. Andrew G Taube and Rodney J Bartlett. New perspectives on unitary coupled-cluster theory. International journal of quantum chemistry, 106(15):3393–3401, 2006. URL: https://onlinelibrary.wiley.com/doi/full/10.1002/qua.21198, doi:10.1002/qua.21198.

  24. Sergey B Bravyi and Alexei Yu Kitaev. Fermionic quantum computation. Annals of Physics, 298(1):210–226, 2002. arXiv: https://arxiv.org/abs/quant-ph/0003137. doi:https://doi.org/10.1006/aphy.2002.6254.

  25. Joonho Lee, William J Huggins, Martin Head-Gordon, and K Birgitta Whaley. Generalized unitary coupled cluster wave functions for quantum computation. Journal of Chemical Theory and Computation, 15(1):311–324, 2018. arXiv: https://arxiv.org/abs/1810.02327. URL: https://pubs.acs.org/doi/10.1021/acs.jctc.8b01004, doi:https://doi.org/10.1021/acs.jctc.8b01004.

  26. Mario Motta, Erika Ye, Jarrod R McClean, Zhendong Li, Austin J Minnich, Ryan Babbush, and Garnet Kin Chan. Low rank representations for quantum simulation of electronic structure. npj Quantum Information, 7(1):1–7, 2021. arXiv: https://arxiv.org/abs/1808.02625. URL: https://www.nature.com/articles/s41534-021-00416-z, doi:https://doi.org/10.1038/s41534-021-00416-z.

  27. Yuta Matsuzawa and Yuki Kurashige. Jastrow-type decomposition in quantum chemistry for low-depth quantum circuits. Journal of Chemical Theory and Computation, 16(2):944–952, 2020. arXiv: https://arxiv.org/abs/1909.12410. URL: https://pubs.acs.org/doi/10.1021/acs.jctc.9b00963, doi:https://doi.org/10.1021/acs.jctc.9b00963.

  28. Ian D Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush. Quantum simulation of electronic structure with linear depth and connectivity. Physical Review Letters, 120(11):110501, 2018. arXiv: https://arxiv.org/abs/1711.04789. URL: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.120.110501, doi:10.1103/PhysRevLett.120.110501.

  29. Kanav Setia, Sergey Bravyi, Antonio Mezzacapo, and James D. Whitfield. Superfast encodings for fermionic quantum simulation. Physical Review Research, 1:033033, 10 2019. arXiv: https://arxiv.org/abs/1810.05274. URL: https://link.aps.org/doi/10.1103/PhysRevResearch.1.033033, doi:10.1103/PhysRevResearch.1.033033.

  30. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv: https://arxiv.org/abs/1411.4028, 2014.

  31. Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34, 2019. arXiv: https://arxiv.org/abs/1709.03489. URL: https://www.mdpi.com/1999-4893/12/2/34, doi:https://doi.org/10.3390/a12020034.

  32. Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv: https://arxiv.org/abs/1812.11075, 2018. URL: https://arxiv.org/abs/1812.11075.

  33. Mauro ES Morales, JD Biamonte, and Zoltán Zimborás. On the universality of the quantum approximate optimization algorithm. Quantum Information Processing, 19(9):1–26, 2020. arXiv: https://arxiv.org/abs/1909.03123. URL: https://link.springer.com/article/10.1007/s11128-020-02748-9, doi:10.1007/s11128-020-02748-9.

  34. Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv: https://arxiv.org/abs/1602.07674, 2016. URL: https://arxiv.org/abs/1602.07674.

  35. Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Physical Review Letters, 125(26):260505, 2020. arXiv: https://arxiv.org/abs/1910.08980. doi:10.1103/PhysRevLett.125.260505.

  36. Matthew B Hastings. Classical and quantum bounded depth approximation algorithms. arXiv: https://arxiv.org/abs/1905.07047, 2019.

  37. Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: a typical case. arXiv: https://arxiv.org/abs/2004.09002, 2020.

  38. Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: worst case examples. arXiv: https://arxiv.org/abs/2005.08747, 2020.

  39. Sami Boulebnane and Ashley Montanaro. Solving boolean satisfiability problems with the quantum approximate optimization algorithm. arXiv: https://arxiv.org/abs/2208.06909, 2022.

  40. Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. arXiv: https://arxiv.org/abs/2308.02342, 2023.

  41. Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick Coles. Variational quantum linear solver. arXiv: https://arxiv.org/abs/1909.05820, 2019. URL: https://arxiv.org/abs/1909.05820.

  42. Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan. Variational algorithms for linear algebra. Science Bulletin, 66(21):2181–2188, 2021. arXiv: https://arxiv.org/abs/1909.03898. URL: https://www.sciencedirect.com/science/article/pii/S2095927321004631, doi:https://doi.org/10.1016/j.scib.2021.06.023.

  43. Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost. Near-term quantum algorithms for linear systems of equations with regression loss functions. New Journal of Physics, 23(11):113021, 11 2021. arXiv: https://arxiv.org/abs/1909.07344. URL: https://dx.doi.org/10.1088/1367-2630/ac325f, doi:10.1088/1367-2630/ac325f.

  44. Eric Anschuetz, Jonathan Olson, Alán Aspuru-Guzik, and Yudong Cao. Variational quantum factoring. In Quantum Technology and Optimization Problems, 74–85. Springer, 2019. arXiv: https://arxiv.org/abs/1808.08927. URL: https://link.springer.com/chapter/10.1007/978-3-030-14082-3\_7, doi:10.1007/978-3-030-14082-3\_7.

  45. Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles. Quantum-assisted quantum compiling. Quantum, 3:140, 2019. arXiv: https://arxiv.org/abs/1807.00800. URL: https://quantum-journal.org/papers/q-2019-05-13-140/, doi:https://doi.org/10.22331/q-2019-05-13-140.

  46. Maria Schuld, Alex Bocharov, Krysta M. Svore, and Nathan Wiebe. Circuit-centric quantum classifiers. arXiv: https://arxiv.org/abs/1804.00633, 2018.

  47. Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical Review Letters, 122(4):040504, 2019. arXiv: https://arxiv.org/abs/1803.07128. URL: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.122.040504, doi:10.1103/PhysRevLett.122.040504.

  48. Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567(7747):209–212, 2019. arXiv: https://arxiv.org/abs/1804.11326. URL: https://www.nature.com/articles/s41586-019-0980-2, doi:10.1038/s41586-019-0980-2.

  49. Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 15(12):1273–1278, 2019. arXiv: https://arxiv.org/abs/1810.03787. URL: https://www.nature.com/articles/s41567-019-0648-8, doi:10.1038/s41567-019-0648-8.

  50. Guillaume Verdon, Michael Broughton, and Jacob Biamonte. A quantum algorithm to train neural networks using low-depth circuits. arXiv: https://arxiv.org/abs/1712.05304, 2017. URL: https://arxiv.org/abs/1712.05304.

  51. Marcello Benedetti, Delfina Garcia-Pintos, Oscar Perdomo, Vicente Leyton-Ortega, Yunseong Nam, and Alejandro Perdomo-Ortiz. A generative modeling approach for benchmarking and training shallow quantum circuits. npj Quantum Information, 5(1):1–9, 2019. arXiv: https://arxiv.org/abs/1801.07686. URL: https://www.nature.com/articles/s41534-019-0157-8, doi:10.1038/s41534-019-0157-8.

  52. Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2(3):033125, 2020. arXiv: https://arxiv.org/abs/1810.11922. URL: https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.2.033125, doi:10.1103/PhysRevResearch.2.033125.

  53. Jonathan Romero, Jonathan P. Olson, and Alan Aspuru-Guzik. Quantum autoencoders for efficient compression of quantum data. Quantum Science and Technology, 2(4):045001, 2017. arXiv: https://arxiv.org/abs/1612.02806. doi:10.1088/2058-9565/aa8072.

  54. Kwok Ho Wan, Oscar Dahlsten, Hlér Kristjánsson, Robert Gardner, and MS Kim. Quantum generalisation of feedforward neural networks. npj Quantum Information, 3(1):36, 2017. arXiv: https://arxiv.org/abs/1612.01045. URL: https://www.nature.com/articles/s41534-017-0032-4, doi:https://doi.org/10.1038/s41534-017-0032-4.

  55. Guillaume Verdon, Jason Pye, and Michael Broughton. A universal training algorithm for quantum deep learning. arXiv: https://arxiv.org/abs/1806.09729, 2018. URL: https://arxiv.org/abs/1806.09729.

  56. Jonathan Romero and Alán Aspuru-Guzik. Variational quantum generators: generative adversarial quantum machine learning for continuous distributions. Advanced Quantum Technologies, 4(1):2000003, 2021. arXiv: https://arxiv.org/abs/1901.00848. doi:10.1002/qute.202000003.

  57. Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan H. S. Derks, Paul K. Faehrmann, and Johannes Jakob Meyer. Training quantum embedding kernels on near-term quantum computers. Physical Review A, 106:042431, 10 2022. arXiv: https://arxiv.org/abs/2105.02276. URL: https://link.aps.org/doi/10.1103/PhysRevA.106.042431, doi:10.1103/PhysRevA.106.042431.

  58. MV Altaisky. Quantum neural network. arXiv: https://arxiv.org/abs/quant-ph/0107012, 2001. URL: https://arxiv.org/abs/quant-ph/0107012.

  59. Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv: https://arxiv.org/abs/1802.06002, 2018.

  60. Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf. Training deep quantum neural networks. Nature Communications, 11(1):808, 2020. arXiv: https://arxiv.org/abs/1902.10445. URL: https://www.nature.com/articles/s41467-020-14454-2, doi:https://doi.org/10.1038/s41467-020-14454-2.

  61. Edward Grant, Marcello Benedetti, Shuxiang Cao, Andrew Hallam, Joshua Lockhart, Vid Stojevic, Andrew G Green, and Simone Severini. Hierarchical quantum classifiers. npj Quantum Information, 4(1):65, 2018. arXiv: https://arxiv.org/abs/1804.03680. URL: https://www.nature.com/articles/s41534-018-0116-9, doi:https://doi.org/10.1038/s41534-018-0116-9.

  62. William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and E Miles Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and Technology, 4(2):024001, 2019. arXiv: https://arxiv.org/abs/1803.11537. URL: https://iopscience.iop.org/article/10.1088/2058-9565/aaea94, doi:10.1088/2058-9565/aaea94.

  63. M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nature Reviews Physics, pages 625–644, 2021. arXiv: https://arxiv.org/abs/2012.09265. doi:10.1038/s42254-021-00348-9.

  64. Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, and others. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics, 94(1):015004, 2022. arXiv: https://arxiv.org/abs/2101.08448. URL: https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.94.015004, doi:10.1103/RevModPhys.94.015004.