Quantum adiabatic machine learning | Quantum Information Processing Skip to main content
Springer Nature Link
Log in

Quantum adiabatic machine learning

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

We develop an approach to machine learning and anomaly detection via quantum adiabatic evolution. This approach consists of two quantum phases, with some amount of classical preprocessing to set up the quantum problems. In the training phase we identify an optimal set of weak classifiers, to form a single strong classifier. In the testing phase we adiabatically evolve one or more strong classifiers on a superposition of inputs in order to find certain anomalous elements in the classification space. Both the training and testing phases are executed via quantum adiabatic evolution. All quantum processing is strictly limited to two-qubit interactions so as to ensure physical feasibility. We apply and illustrate this approach in detail to the problem of software verification and validation, with a specific example of the learning phase applied to a problem of interest in flight control systems. Beyond this example, the algorithm can be used to attack a broad class of anomaly detection problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Random number generation may appear to be a counterexample, as it is multi-valued, but only over different calls to the random-number generator.

  2. One important consideration is that, as we shall see below, for practical reasons we may only be able to track errors at the level of one-bit errors and correlations between bit-pairs. Such limited tracking can be alleviated to some extent by using intermediate spaces, where higher order correlations between bits appearing at the level of the output space may not yet have had time to develop.

  3. This inequality reflects the fact that for \(n\) overlapping sets, \(P\left[\bigcup _{i=1}^{n}s_i\right]=\sum _{i=1}^{n}P[s_i]-\sum _{i\ne j}P[s_i\cap s_j] + \sum _{i\ne j \ne k}P[s_i\cap s_j \cap s_k] - \sum _{i\ne j\ne k \ne m}P[s_i\cap s_j \cap s_k \cap s_m]+\dots \) Each term is larger than the next in the series; \(n+1\) sets cannot intersect where \(n\) sets do not. Our truncation of the series is greater than or equal to the full value because we stop after a subtracted term.

  4. Any Boolean function of \(\ell \) variables can be uniquely expanded in the form \(f_i(x_1,\dots ,x_\ell ) = \sum _{\alpha =0}^{2^\ell -1} \epsilon _{i\alpha } s_{\alpha }\), where \(\epsilon _{i\alpha }\in \{0,1\}\) and \(s_\alpha \) are the \(2^\ell \) “simple” Boolean functions \(s_0 = x_1 x_2 \cdots x_\ell \), \(s_1 = x_1 x_2 \cdots \overline{x_\ell }\), \(\dots \), \(s_{2^\ell -1} = \overline{x_1}\, \overline{x_2} \cdots \overline{x_\ell }\), where \(\overline{x}\) denotes the negation of the bit \(x\). Since each \(\epsilon _{i\alpha }\) can assume one of two values, there are \(2^{2^\ell }\) different Boolean functions.

  5. We are grateful to Greg Tallant from the Lockheed Martin Corporation for providing us with this problem as an example of interest in flight control systems.

References

  1. Vapnik, V.N.: Statistical Learning Theory. Wiley, London (1998)

    MATH  Google Scholar 

  2. Servedio, R.A., Gortler, S.J.: Equivalences and separations between quantum and classical learnability. SIAM J. Comput. 33, 1067 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  3. Aïmeur, E., Brassard, G., Gambs, S.: Machine learning in a quantum world. In: Lamontagne, L., Marchand, M. (eds.) Advances in Artificial Intelligence, vol. 4013 of Lecture Notes in Computer Science, p. 431. Springer, Berlin (2006)

  4. Meir, R., Rätsch, G.: An introduction to boosting and leveraging. In: Mendelson, S., Smola, A. (eds.) Advanced Lectures on Machine Learning, vol. 2600 of Lecture Notes in Computer Science, p. 118. Springer, Berlin (2003)

  5. Freund, Y., Schapire, R., Abe, N.: A short introduction to boosting. J. Jpn. Soc. Artif. Intell. 14, 771 (1999)

    Google Scholar 

  6. Neven, H., Denchev, V.S., Rose, G., Macready, W.G.: Training a binary classifier with the quantum adiabatic algorithm. eprint arXiv:0811.0416

  7. Neven, H., Denchev., V.S., Drew-Brook, M., Zhang, J., Macready, W.G., Rose, G.: NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing (2009)

  8. Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: A survey. ACM Comput. Surv. (CSUR) 41(3), 15 (2009)

    Article  Google Scholar 

  9. Dijkstra, E.W.: Notes on structured programming. In: Dahl, O.-J., Dijkstra, E.W., Hoare, C.A.R. (eds.) Structured Programming, p. 1. Academic Press, New York (1972)

    Google Scholar 

  10. Tassey, G.: The economic impacts of inadequate infrastructure for software testing. National Institute of Standards and Technology, RTI Project 7007.011 (2002)

  11. Bryce, R., Kuhn, R., Lei, Y., Kacker, R.: Combinatorial testing. In: Ramachandran, M., de Carvalho, R.A. (eds.) Handbook of Software Engineering Research and Productivity Technologies, p. 196. IGI Global (2009)

  12. Kuhn, D.R., Kacker, R.N., Lei, Y.: Practical combinatorial testing. NIST Special, Publication 800–142 (2010)

  13. Grindal, M., Offutt, J., Andler, S.F.: Combination Testing Strategies: A survey. GMU Technical, Report ISE-TR-04-05 (2004)

  14. Cohen, D.M., Dalal, S.R., Parelius, J., Patton, G.C.: The combinatorial design approach to automatic test generation. Softw. IEEE 13, 83 (1996)

    Article  Google Scholar 

  15. D’Silva, V., Kroening, D., Weissenbacher, G.: A survey of automated techniques for formal software verification. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27, 1165 (2008)

    Article  Google Scholar 

  16. Weber, T., Amjad, H.: Efficiently checking propositional refutations in HOL theorem provers. J. Appl. Log. 7, 26 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  17. Neven, H., Rose, G., Macready, W.G.: Image recognition with an adiabatic quantum computer I. mapping to quadratic unconstrained binary optimization. eprint arXiv:0804.4457

  18. Neven, H., Denchev, V.S., Rose, G., Macready, W.G.: Training a large scale classifier with the quantum adiabatic algorithm. eprint arXiv:0912.0779

  19. Bian, Z., Chudak, F., Macready, W.G., Rose, G.: The Ising model: teaching an old problem new tricks. D-Wave Systems (2010)

  20. Schapire, R.E.: The strength of weak learnability. Mach. Learn. 5, 197 (1990)

    Google Scholar 

  21. Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. eprint quant-ph/0001106

  22. Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292(5516), 472 (2001)

    Article  ADS  MATH  MathSciNet  Google Scholar 

  23. Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., Regev, O.: Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37, 166 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  24. Mizel, A., Lidar, D.A., Mitchell, M.: Simple proof of equivalence between adiabatic quantum computation and the circuit model. Phys. Rev. Lett. 99, 070502 (2007)

    Article  ADS  Google Scholar 

  25. Jordan, S.P., Farhi, E., Shor, P.W.: Error-correcting codes for adiabatic quantum computation. Phys. Rev. A 74, 052322 (2006)

    Article  ADS  MathSciNet  Google Scholar 

  26. Lidar, Daniel A.: Towards fault tolerant adiabatic quantum computation. Phys. Rev. Lett. 100, 160506 (2008)

    Article  ADS  Google Scholar 

  27. Childs, Andrew M., Edward, Farhi, John, Preskill: Robustness of adiabatic quantum computation. Phys. Rev. A 65, 012322 (2001)

    Article  Google Scholar 

  28. Sarandy, M.S., Lidar, D.A.: Adiabatic quantum computation in open systems. Phys. Rev. Lett. 95, 250503 (2005)

    Article  ADS  Google Scholar 

  29. Stehle, E., Lynch, K., Shevertalov, M., Rorres, C., Mancoridis, S.: On the use of computational geometry to detect software faults at runtime. ICAC10, June 711. Washington, DC, USA (2010)

  30. Le Traon, Y., Baudry, B., Jezequel, J.-M.: Design by contract to improve software vigilance. IEEE Trans. Softw. Eng. 32, 571 (2006)

    Article  Google Scholar 

  31. Mannor, S., Meir, R.: Geometric bounds for generalization in boosting. In: Helmbold, D., Williamson, B. (eds.) Computational Learning Theory, vol. 2111 of Lecture Notes in Computer Science, pp. 461–472. Springer, Berlin (2001)

  32. Kotsiantis, S.B.: Supervised machine learning: A review of classification techniques. Informatica 31, 249 (2007)

    MATH  MathSciNet  Google Scholar 

  33. Yu, L., Liu, H.: Efficient feature selection via analysis of relevance and redundancy. J. Mach. Learn. Res. 5, 1205 (2004)

    MATH  Google Scholar 

  34. Zhang, S., Zhang, C., Yang, Q.: Data preparation for data mining. Appl. Artif. Intell. 17, 375 (2003)

    Article  Google Scholar 

  35. Cheng, H., Yan, X., Han, J., Hsu, C.-W.: Discriminative frequent pattern analysis for effective classification. In: International Conference on Data Engineering, p. 716 (2007)

  36. Breiman, L.: Arcing classifiers. Ann. Stat. 26, 801 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  37. Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Occam’s razor. Inf. Process. Lett. 24, 377 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  38. Biamonte, J.D., Peter, Love: Realizable Hamiltonians for universal adiabatic quantum computers. Phys. Rev. A 78, 012352 (2008)

    Article  ADS  MathSciNet  Google Scholar 

  39. Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  40. Karimi, K., Dickson, N.G., Hamze, F., Amin, M.H.S., Drew-Brook, M., Chudak, F.A., Bunyk, P.I., Macready, W.G., Rose, G.: Investigating the performance of an adiabatic quantum optimization processor. Quantum Inf. Process. 11(1), 77 (2012)

    Google Scholar 

  41. Harris, R., Johnson, M.W., Lanting, T., Berkley, A.J., Johansson, J., Bunyk, P., Tolkacheva, E., Ladizinsky, E., Ladizinsky, N., Oh, T., Cioata, F., Perminov, I., Spear, P., Enderud, C., Rich, C., Uchaikin, S., Thom, M.C., Chapple, E.M., Wang, J., Wilson, B., Amin, M.H.S., Dickson, N., Karimi, K., Macready, W., Truncik, C.J.S., Rose, G.: Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511 (2010)

    Article  ADS  Google Scholar 

  42. Cheng, H., Yan, X., Han, J., Hsu, C.-W.: Discriminative frequent pattern analysis for effective classification. In: IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey (2007)

  43. Teufel, S.: Adiabatic Perturbation Theory in Quantum Dynamics. Springer, Berlin (2003)

    Book  MATH  Google Scholar 

  44. Jansen, S., Ruskai, M.-B., Seiler, R.: Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys. 48, 102111 (2007)

    Article  ADS  MathSciNet  Google Scholar 

  45. Lidar, D.A., Rezakhani, A.T., Hamma, A.: Adiabatic approximation with exponential accuracy for many-body systems and quantum computation. J. Math. Phys. 50, 102106 (2009)

    Article  ADS  MathSciNet  Google Scholar 

  46. Roland, J., Cerf, N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65, 042308 (2002)

    Article  ADS  Google Scholar 

  47. Rezakhani, A.T., Pimachev, A.K., Lidar, D.A.: Accuracy versus run time in an adiabatic quantum search. Phys. Rev. A 82, 052305 (2010)

    Article  ADS  Google Scholar 

  48. Young, A.P., Knysh, S., Smelyanskiy, V.N.: Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101, 170503 (2008)

    Article  ADS  Google Scholar 

  49. Slepian, D.: On the number of symmetry types of Boolean functions of N variables. Can. J. Math. 5, 185 (1953)

    Article  MATH  MathSciNet  Google Scholar 

  50. Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C–35, 677 (1986)

    Article  Google Scholar 

  51. Jordan, Stephen P., Edward, Farhi: Perturbative gadgets at arbitrary orders. Phys. Rev. A 77, 062329 (2008)

    Article  ADS  Google Scholar 

  52. Rezakhani, A.T., Kuo, W.-J., Hamma, A., Lidar, D.A., Zanardi, P.: Quantum adiabatic brachistochrone. Phys. Rev. Lett. 103, 080502 (2009)

    Article  ADS  Google Scholar 

  53. Rezakhani, A.T., Abasto, D.F., Lidar, D.A., Zanardi, P.: Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions. Phys. Rev. A 82, 012321 (2010)

    Article  ADS  Google Scholar 

Download references

Acknowledgments

The authors are grateful to the Lockheed Martin Corporation for financial support under the URI program. KP is also supported by the NSF under a graduate research fellowship. DAL acknowledges support from the NASA Ames Research Center.

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA, 90089, USA

    Kristen L. Pudenz & Daniel A. Lidar

  2. Departments of Electrical Engineering, Chemistry, and Physics, Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA, 90089, USA

    Daniel A. Lidar

Authors
  1. Kristen L. Pudenz
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Daniel A. Lidar
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Kristen L. Pudenz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pudenz, K.L., Lidar, D.A. Quantum adiabatic machine learning. Quantum Inf Process 12, 2027–2070 (2013). https://doi.org/10.1007/s11128-012-0506-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11128-012-0506-4

Keywords