nach oben

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Ising Models for Binary Clustering via Adiabatic Quantum Computing

verfasst von: Christian Bauckhage, E. Brito, K. Cvejoski, C. Ojeda, Rafet Sifa, S. Wrobel

Erschienen in: Energy Minimization Methods in Computer Vision and Pattern Recognition

Verlag: Springer International Publishing

Einloggen, um Zugang zu erhalten

Abstract

Existing adiabatic quantum computers are tailored towards minimizing the energies of Ising models. The quest for implementations of pattern recognition or machine learning algorithms on such devices can thus be seen as the quest for Ising model (re-)formulations of their objective functions. In this paper, we present Ising models for the tasks of binary clustering of numerical and relational data and discuss how to set up corresponding quantum registers and Hamiltonian operators. In simulation experiments, we numerically solve the respective Schrödinger equations and observe our approaches to yield convincing results.

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Testen Sie jetzt 15 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Jetzt informieren

Nächstes Kapitel Quantum Interference and Shape Detection

Technology Quarterly: Quantum Devices. The Economist, March 2017

Castelvecchi, D.: Quantum computers ready to leap out of the lab in 2017. Nature 541(7635), 9–10 (2017). https://doi.org/10.1038/541009a CrossRef

Gibney, E.: D-Wave upgrade: how scientists are using the world’s most controversial quantum computer. Nature 541(7638), 447–448 (2017). https://doi.org/10.1038/541447b CrossRef

Grover, L.: From Schrödinger’s equation to the quantum search algorithm. J. of Phys. 56(2), 333–348 (2001). https://doi.org/10.1119/1.1359518

Aïmeur, E., Brassard, G., Gambs, S.: Quantum clustering algorithms. In: Proceedings ICML (2007)

Aïmeur, E., Brassard, G., Gambs, S.: Quantum speed-up for unsupervised learning. Mach. Learn. 90(2), 261–287 (2013). https://doi.org/10.1007/s10994-012-531305 MathSciNetCrossRefMATH

Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411 [quant-ph] (2013)

Wiebe, N., Kapoor, A., Svore, K.: Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Inf. Comput. 15(3–4), 316–356 (2015) MathSciNet

Albash, T., Lidar, D.: Adiabatic quantum computing. arXiv:1611.04471 [quant-ph] (2016)

10.

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

11.

Johnson, M., Amin, M., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A., Johansson, J., Bunyk, P., Chapple, E., Enderud, C., Hilton, J., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M., Tolkacheva, E., Truncik, C., Uchaikin, S., Wang, J., Wilson, B., Rose, G.: Quantum annealing with manufactured spins. Nature 473(7346), 194–198 (2011). https://doi.org/10.1038/nature10012 CrossRef

12.

Born, M., Fock, V.: Beweis des Adiabatensatzes. Zeitschrift für Physik 51(3–4), 165–180 (1928). https://doi.org/10.1007/BF01343193 CrossRef

13.

Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982). https://doi.org/10.1109/TIT.1982.1056489 MathSciNetCrossRefMATH

14.

Hartigan, J., Wong, M.: Algorithm AS 136: a \(k\)-means clustering algorithm. J. Roy. Stat. Soc. C 28(1), 100–108 (1979). https://doi.org/10.2307/2346830 MATH

15.

MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings Berkeley Symposium on Mathematical Statistics and Probability (1967)

16.

Aloise, D., Deshapande, A., Hansen, P., Popat, P.: NP-hardness of euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245–248 (2009). https://doi.org/10.1007/s10994-009-5103-0 CrossRefMATH

17.

Fisher, R.: On the probable error of a coefficient correlation deduced from a small sample. Metron 1, 3–32 (1921) MathSciNet

18.

MacKay, D.: Information Theory, Inference, and Learning Algorithms. Cambridge University Press, Cambridge (2003) MATH

19.

Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. PAMI 22(8), 888–905 (2000). https://doi.org/10.1109/34.868688 CrossRef

20.

Dhillon, I.: Co-clustering documents and words using bipartite spectral graph partitioning. In: Proceedings KDD (2001)

21.

von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395–416 (2007). https://doi.org/10.1007/s11222-007-9033-z MathSciNetCrossRef

22.

Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25(4), 619–633 (1975) MathSciNetMATH

23.

Johansson, J., Nation, P., Nori, F.: QuTiP 2: a python framework for the dynamics of open quantum systems. Comput. Phys. Commun. 184(4), 1234–1240 (2013). https://doi.org/10.1016/j.cpc.2012.11.019 CrossRef

24.

Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. arXiv:1611.09347 [quant-ph] (2016)

25.

Dunjiko, V., Taylor, J., Briegel, H.: Quantum-enhanced machine learning. Phys. Rev. Lett. 117(13), 130501 (2016). https://doi.org/10.1103/PhysRevLett.117.130501 MathSciNetCrossRef

26.

Schuld, M., Sinayskiy, I., Petruccione, F.: An introduction to quantum machine learning. Contemp. Phys. 56(2), 172–185 (2014). https://doi.org/10.1080/00107514.2014.964942 CrossRefMATH

27.

Wiebe, N., Kapoor, A., Svore, K.: Quantum perceptron models. In: Proceedings NIPS (2016)

28.

Wittek, P.: Quantum Machine Learning. Academic Press, London (2014) MATH

29.

Ushijima-Mwesigwa, H., Negre, C., Mniszewski, S.: Graph partitioning using quantum annealing on the D-Wave system. arXiv:1705.03082 [quant-ph] (2017)

30.

Newman, M.: Modularity and community structure in networks. PNAS 103(23), 8577–8582 (2006). https://doi.org/10.1073/pnas.0601602103 CrossRef

Titel: Ising Models for Binary Clustering via Adiabatic Quantum Computing
verfasst von: Christian Bauckhage
E. Brito
K. Cvejoski
C. Ojeda
Rafet Sifa
S. Wrobel
Verlag: Springer International Publishing
Buch: Energy Minimization Methods in Computer Vision and Pattern Recognition
Print ISBN: 978-3-319-78198-3

Electronic ISBN: 978-3-319-78199-0

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78199-0_1

Springer Professional

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

Abstract

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner