nach oben

nächstes Kapitel Quantum Interference and Shape Detection

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

Ising Models for Binary Clustering via Adiabatic Quantum Computing

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

Verlag: Springer International Publishing

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

» Jetzt Zugang zum Volltext 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.

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

Jetzt einloggen Kostenlos registrieren

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 + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 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 + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

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

Buch

Energy Minimization Methods in Computer Vision and Pattern Recognition

Print ISBN: 978-3-319-78198-3

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

https://doi.org/10.1007/978-3-319-78199-0

DOI

https://doi.org/10.1007/978-3-319-78199-0_1

Autoren:

Christian Bauckhage
E. Brito
K. Cvejoski
C. Ojeda
Rafet Sifa
S. Wrobel

Verlag

Springer International Publishing

Sequenznummer

Premium Partner

Bildnachweise