2011

Quantum adiabatic machine learning

Pudenz, Kristen L., Lidar, Daniel A.

Understand

We develop an approach to machine learning and anomaly detection via quantum adiabatic evolution.

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.

Built on

On the number of symmetry types of Boolean functions of N N variables
D. Slepian · 1953
Earlier work this paper cites.
Notes on structured programming
E. W. Dijkstra · 1972
Earlier work this paper cites.
Graph-based algorithms for Boolean function manipulation
R.E. Bryant · 1986
Earlier work this paper cites.
Occam’s razor
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1987
Earlier work this paper cites.
The strength of weak learnability
R. E. Schapire · 1990
Earlier work this paper cites.
The combinatorial design approach to automatic test generation
D. M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton · 1996
Earlier work this paper cites.
Statistical Learning Theory
V. N. Vapnik · 1998
Earlier work this paper cites.
Arcing classifiers
L. Breiman · 1998
Earlier work this paper cites.
A short introduction to boosting
Y. Freund, R. Schapire, and N. Abe · 1999
Earlier work this paper cites.
A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda · 2001
Earlier work this paper cites.
Robustness of adiabatic quantum computation
Andrew M. Childs, Edward Farhi, and John Preskill · 2001
Earlier work this paper cites.
Geometric bounds for generalization in boosting
S. Mannor and R. Meir · 2001
Earlier work this paper cites.
The economic impacts of inadequate infrastructure for software testing, 2002
G. Tassey · 2002
Earlier work this paper cites.
Quantum search by local adiabatic evolution
J. Roland and N.J. Cerf · 2002
Earlier work this paper cites.
An introduction to boosting and leveraging
R. Meir and G. Rätsch · 2003
Earlier work this paper cites.
Data preparation for data mining
S. Zhang, C. Zhang, and Q. Yang · 2003
Earlier work this paper cites.
Adiabatic Perturbation Theory in Quantum Dynamics
S. Teufel · 2003
Earlier work this paper cites.

Similar

Equivalences and separations between quantum and classical learnability
R. A. Servedio and S. J. Gortler · 2004
Cited alongside, same era.
Combination testing strategies: A survey, 2004
M. Grindal, J. Offutt, and S. F. Andler · 2004
Cited alongside, same era.
Efficient feature selection via analysis of relevance and redundancy
L. Yu and H. Liu · 2004
Cited alongside, same era.
Adiabatic quantum computation in open systems
M. S. Sarandy and D. A. Lidar · 2005
Cited alongside, same era.
Machine learning in a quantum world
Esma Aïmeur, Gilles Brassard, and Sébastien Gambs · 2006
Cited alongside, same era.
Error-correcting codes for adiabatic quantum computation
S.P. Jordan, E. Farhi, and P.W. Shor · 2006
Cited alongside, same era.
Design by contract to improve software vigilance
Y. Le Traon, B. Baudry, and J.-M. Jezequel · 2006
Cited alongside, same era.
Adiabatic quantum computation is equivalent to standard quantum computation
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev · 2007
Cited alongside, same era.
Simple proof of equivalence between adiabatic quantum computation and the circuit model
A. Mizel, D. A. Lidar, and M. Mitchell · 2007
Cited alongside, same era.
Supervised machine learning: A review of classification techniques
S. B. Kotsiantis · 2007
Cited alongside, same era.
Discriminative frequent pattern analysis for effective classification
H. Cheng, X. Yan, J. Han, and C.-W. Hsu · 2007
Cited alongside, same era.
Discriminative frequent pattern analysis for effective classification
H. Cheng, X. Yan, J. Han, and C.-W. Hsu · 2007
Cited alongside, same era.

Then

Minor-embedding in adiabatic quantum computation: I. the parameter setting problem
V. Choi · 2008
Later among the works it cites.
Size dependence of the minimum excitation gap in the quantum adiabatic algorithm
A. P. Young, S. Knysh, and V. N. Smelyanskiy · 2008
Later among the works it cites.
Perturbative gadgets at arbitrary orders
Stephen P. Jordan and Edward Farhi · 2008
Later among the works it cites.
NIPS 2009 demonstration: Binary classiﬁcation using hardware implementation of quantum annealing
H. Neven et al · 2009
Later among the works it cites.
Anomaly detection: A survey
Varun Chandola, Arindam Banerjee, and Vipin Kumar · 2009
Later among the works it cites.
Combinatorial testing
R. Bryce, R. Kuhn, Y. Lei, and R. Kacker · 2009
Later among the works it cites.
Efficiently checking propositional refutations in hol theorem provers
T. Weber and H. Amjad · 2009
Later among the works it cites.
Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
D. A. Lidar, A. T. Rezakhani, and A. Hamma · 2009
Later among the works it cites.
Quantum adiabatic brachistochrone
A. T. Rezakhani, W.-J. Kuo, A. Hamma, D.A. Lidar, and P. Zanardi · 2009
Later among the works it cites.
Practical combinatorial testing, 2010
D. R. Kuhn, R. N. Kacker, and Y. Lei · 2010
Later among the works it cites.
The Ising model: teaching an old problem new tricks
Z. Bian, F. Chudak, W. G. Macready, and G. Rose · 2010
Later among the works it cites.
On the use of computational geometry to detect software faults at runtime
E. Stehle, K. Lynch, M. Shevertalov, C. Rorres, and Spiros Mancoridis · 2010
Later among the works it cites.
Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor
R. Harris, M. W. Johnson, T. Lanting, A. J. Berkley, J. Johansson, P. Bunyk, E. Tolkacheva, E. Ladizinsky, N. Ladizinsky, T. Oh, F. Cioata, I. Perminov, P. Spear, C. Enderud, C. Rich, S. Uchaikin, M. C. Thom, E. M. Chapple, J. Wang, B. Wilson, M. H. S. Amin, N. Dickson, K. Karimi, W. Macready, C. J. S. Truncik, and G. Rose · 2010
Later among the works it cites.
Accuracy versus run time in an adiabatic quantum search
A. T. Rezakhani, A. K. Pimachev, and D. A. Lidar · 2010
Later among the works it cites.
Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
A.T. Rezakhani, D.F. Abasto, D.A. Lidar, and P. Zanardi · 2010
Later among the works it cites.
Investigating the performance of an adiabatic quantum optimization processor
K. Karimi, N. Dickson, F. Hamze, M. Amin, M. Drew-Brook, F. Chudak, P. Bunyk, W. Macready, and G. Rose · 2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…