CoChat
Sign Up
Cited by 19Quantum Computing Algorithms and ArchitectureGaussian Processes and Bayesian InferenceQuantum Information and Cryptography

Quantum algorithms for training Gaussian processes

Open access
Zhao, Zhikuan, Fitzsimons, Jack K., Osborne, Michael A., Roberts, Stephen J., Fitzsimons, Joseph F.·2019·Physical Review A
DOI 10.1103/physreva.100.012304
Open this paper in CoChat — free accountOpen PDF

Abstract

Gaussian processes (GPs) are important models in supervised machine learning. Training in Gaussian processes refers to selecting the covariance functions and the associated parameters in order to improve the outcome of predictions, the core of which amounts to evaluating the logarithm of the marginal likelihood ($\mathrm{LML}$) of a given model. The $\mathrm{LML}$ gives a concrete measure of the quality of prediction that a GP model is expected to achieve. The classical computation of the $\mathrm{LML}$ typically carries a polynomial time overhead with respect to the input size. We propose a quantum algorithm that computes the logarithm of the determinant of a Hermitian matrix, which runs in logarithmic time for sparse matrices. This is applied in conjunction with a variant of the quantum linear system algorithm that allows for logarithmic-time computation of the form ${\mathbf{y}}^{T}{A}^{\ensuremath{-}1}\mathbf{y}$, where $\mathbf{y}$ is a dense vector and $A$ is the covariance matrix. We hence show that quantum computing can be used to estimate the $\mathrm{LML}$ of a GP with exponentially improved efficiency under certain conditions.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physreva.100.012304

Cites

28 of 28 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The HHL-based algorithm was extended to compute the logarithm of the marginal likelihood, a crucial step for hyperparameter optimization.

    “More importantly, this algorithm was extended to compute the logarithm of the marginal likelihood [70], which is a crucial step for hyperparameter optimization.”

    From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [70]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

1 of the 29 references couldn’t be matched to a known paper.

Research works printed but not linked: 25

  1. [2]C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning series) (The MIT Press, 2005), ISBN 026218253X.
  2. [4]A. W. Harrow, A. Hassidim, and S. Lloyd, Physical Review Letters 103 , 150502 (2009).
  3. [7]S. Lloyd, M. Mohseni, and P. Rebentrost, arXiv preprint arXiv:1307.0411 (2013). · arXiv
  4. [8]P. Rebentrost, M. Mohseni, and S. Lloyd, Physical review letters 113 , 130503 (2014).
  5. [9]N. Wiebe, A. Kapoor, and K. M. Svore, arXiv preprint arXiv:1412.3489 (2014). · arXiv
  6. [10]M. Schuld, I. Sinayskiy, and F. Petruccione, arXiv preprint arXiv:1601.07823 (2016). · arXiv
  7. [11]H. Neven, V. S. Denchev, G. Rose, and W. G. Macready, arXiv preprint arXiv:0811.0416 (2008). · arXiv
  8. [13]M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko, arXiv preprint arXiv:1601.02036 (2016). · arXiv
  9. [14]J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic, arXiv preprint arXiv:1512.02900 (2015). · arXiv
  10. [15]Z. Zhao, J. K. Fitzsimons, and J. F. Fitzsimons, arXiv preprint arXiv:1512.03929 (2015). · arXiv
  11. [17]J. Quiñonero-Candela and C. E. Rasmussen, Journal of Machine Learning Research 6 , 1939 (2005).
  12. [18]V. Minden, A. Damle, K. L. Ho, and L. Ying, arXiv preprint arXiv:1603.08057 (2016). · arXiv
  13. [20]C. Boutsidis, P. Drineas, P. Kambadur, and A. Zouzias, arXiv preprint arXiv:1503.00374 (2015). · arXiv
  14. [21]H. Avron and S. Toledo, Journal of the ACM (JACM) 58 , 8 (2011).
  15. [23]A. Y. Kitaev, arXiv preprint quant-ph/9511026 (1995). · arXiv
  16. [24]V. Bužek, R. Derka, and S. Massar, Physical review letters 82 , 2207 (1999).
  17. [25]A. Luis and J. Peˇ rina, Physical review A 54 , 4564 (1996).
  18. [26]R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, in Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences (The Royal Society, 1998), vol. 454, pp. 339-354.
  19. [27]N. Liu, J. Thompson, C. Weedbrook, S. Lloyd, V. Vedral, M. Gu, and K. Modi, arXiv preprint arXiv:1510.04758 (2015). · arXiv
  20. [28]V. Giovannetti, S. Lloyd, and L. Maccone, Physical Review Letters 100 , 160501 (2008).
  21. [29]D. W. Berry, A. M. Childs, and R. Kothari, in Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on (IEEE, 2015), pp. 792-809.
  22. [30]D. W. Berry and A. M. Childs, arXiv preprint arXiv:0910.4157 (2009). · arXiv
  23. [31]A. Melkumyan and F. Ramos, in IJCAI (2009), vol. 9, pp. 1936-1942.
  24. [34]L. Wossnig, Z. Zhao, and A. Prakash, arXiv preprint arXiv:1704.06174 (2017). · arXiv
  25. [36]I. Kerenidis and A. Prakash, arXiv preprint arXiv:1704.04992 (2017). · arXiv

Cited by

Sorted by citations

Related

Authors
Zhao, Z., Fitzsimons, J. K., Osborne, M. A., Roberts, S. J., & Fitzsimons, J. F.
Affiliations
  • Centre for Quantum Technologies (SG)
  • University of Oxford (GB)
ORCID
Venue
Physical Review A
Publisher
American Physical Society (APS)
Published
2019-07-08
Volume
100
Issue
1
ISSN
  • 0556-2791 (ISSN-L)
  • 2469-9926
  • 2469-9934
DOI
10.1103/physreva.100.012304
OpenAlex
W2795095398
Cited by
19
References
29
Citations by year
2026: 2 · 2025: 2 · 2023: 4 · 2022: 1 · 2021: 2 · 2020: 7 · 2019: 1
FWCI
1.27
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Ministry of Education - Singapore
  • Air Force Office of Scientific Research (FA2386-15-1-4082)
  • National Research Foundation Singapore (NRF-NRFF2013-01)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Gaussian Processes and Bayesian Inference
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
Gaussian processes, quantum algorithms, marginal likelihood, sparse matrices, quantum machine learning, computational complexity

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review