Skip to main content
Top
Published in: Quantum Information Processing 6/2020

01-06-2020

Emulation of high-performance correlation-based quantum clustering algorithm for two-dimensional data on FPGA

Authors: Talal Bonny, A. Haq

Published in: Quantum Information Processing | Issue 6/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Clustering algorithms are used to classify the unlabeled data into a number of categories with polynomial time complexity. Quantum clustering algorithms are developed to improve the performance and to achieve higher gain. In this work, we implement the quantum k-means clustering algorithm on field-programmable gate array (FPGA) by exploiting the implicit parallelism of the FPGA technology to achieve high speed among the software-implemented recent proposals. To do that, we establish a new method to measure the inner product between two qubits which is based on the correlation between the Euclidean distance and the inner product. We also optimize the quantum gates in terms of speed and removing the discretization error. Experimental results show a reduction in the running time by 500× as compared to the classical k-means algorithm for the A1 standard dataset.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 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

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD’96), Evangelos Simoudis, Jiawei Han, and Usama Fayyad (Eds.). AAAI Press, pp. 226–231 (1996) Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD’96), Evangelos Simoudis, Jiawei Han, and Usama Fayyad (Eds.). AAAI Press, pp. 226–231 (1996)
3.
go back to reference Pakhira, M.K.: A linear time-complexity k-means algorithm using cluster shifting. In: 2014 International Conference on Computational Intelligence and Communication Networks, Bhopal, pp. 1047–1051 (2014) Pakhira, M.K.: A linear time-complexity k-means algorithm using cluster shifting. In: 2014 International Conference on Computational Intelligence and Communication Networks, Bhopal, pp. 1047–1051 (2014)
4.
go back to reference Bifet, A.: Machine Learning for Data Streams, Chapter 9. MIT Press, Cambridge (2018)CrossRef Bifet, A.: Machine Learning for Data Streams, Chapter 9. MIT Press, Cambridge (2018)CrossRef
7.
go back to reference Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef
8.
go back to reference Mahmud, N., El-Araby, E., Caliga, D.: Scaling reconfigurable emulation of quantum algorithms at high precision and high throughput. Quantum Eng 1(2), e19 (2019)CrossRef Mahmud, N., El-Araby, E., Caliga, D.: Scaling reconfigurable emulation of quantum algorithms at high precision and high throughput. Quantum Eng 1(2), e19 (2019)CrossRef
9.
go back to reference Xin, T.: A novel approach for emulating quantum computers on classical platforms. Quantum Eng 1(2), e18 (2019)CrossRef Xin, T.: A novel approach for emulating quantum computers on classical platforms. Quantum Eng 1(2), e18 (2019)CrossRef
10.
12.
go back to reference Pilch, J., Długopolski, J.: An FPGA-based real quantum computer emulator. J. Comput. Electron. 18(1), 329–342 (2019)CrossRef Pilch, J., Długopolski, J.: An FPGA-based real quantum computer emulator. J. Comput. Electron. 18(1), 329–342 (2019)CrossRef
13.
go back to reference Lee, Y.H., Khalil-Hani, M., Marsono, M.N.: An FPGA-based quantum computing emulation framework based on serial-parallel architecture. Int. J. Reconfig. Comput. 2016, 5718124, 18 pages (2016) Lee, Y.H., Khalil-Hani, M., Marsono, M.N.: An FPGA-based quantum computing emulation framework based on serial-parallel architecture. Int. J. Reconfig. Comput. 2016, 5718124, 18 pages (2016)
14.
go back to reference Hu, F., Wang, B.N., Wang, N., et al.: Quantum machine learning with D-wave quantum computer. Quantum Eng. 1(2), e12 (2019) Hu, F., Wang, B.N., Wang, N., et al.: Quantum machine learning with D-wave quantum computer. Quantum Eng. 1(2), e12 (2019)
15.
go back to reference Britt, B.C.: Modeling viral diffusion using quantum computational network simulation. Quantum Eng. 2(1), e29 (2020)CrossRef Britt, B.C.: Modeling viral diffusion using quantum computational network simulation. Quantum Eng. 2(1), e29 (2020)CrossRef
16.
go back to reference Wang, S.H., Long, G.L.: Big data and quantum computation. Chin. Sci. Bull. 60(5–6), 499–508 (2015)CrossRef Wang, S.H., Long, G.L.: Big data and quantum computation. Chin. Sci. Bull. 60(5–6), 499–508 (2015)CrossRef
19.
go back to reference Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219 (1996) Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219 (1996)
23.
go back to reference Khalid, A.U., Zilic, Z., Radecka, K.: FPGA emulation of quantum circuits. In: Proceedings of the IEEE International Conference on Computer Design (ICCD’04). IEEE Computer Society, Washington, DC, USA, pp. 310–315 (2004) Khalid, A.U., Zilic, Z., Radecka, K.: FPGA emulation of quantum circuits. In: Proceedings of the IEEE International Conference on Computer Design (ICCD’04). IEEE Computer Society, Washington, DC, USA, pp. 310–315 (2004)
24.
go back to reference MATLAB, 2017. an 9.3 (R2017b), Natick, Massachusetts: The MathWorks Inc MATLAB, 2017. an 9.3 (R2017b), Natick, Massachusetts: The MathWorks Inc
28.
go back to reference Jin, X., Han, J.: K-means clustering. In: Sammut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning. Springer, Boston (2011) Jin, X., Han, J.: K-means clustering. In: Sammut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning. Springer, Boston (2011)
29.
go back to reference Arthur, D., Vassilvitskii, S.: K-means++: the advantages of careful seeding. In: 19th SODA (2007), pp. 1027–1035 Arthur, D., Vassilvitskii, S.: K-means++: the advantages of careful seeding. In: 19th SODA (2007), pp. 1027–1035
30.
go back to reference Malinen, M.I., Mariescu-Istodor, R., Fränti, P.: K-means*: clustering by gradual data transformation. Pattern Recognit. 47, 3376–3386 (2014)CrossRef Malinen, M.I., Mariescu-Istodor, R., Fränti, P.: K-means*: clustering by gradual data transformation. Pattern Recognit. 47, 3376–3386 (2014)CrossRef
31.
go back to reference Lai, J.Z., Huang, T.J., Liaw, Y.C.: A fast k-means clustering algorithm using cluster center displacement. Pattern Recognit. 42(11), 2551–2556 (2009)CrossRef Lai, J.Z., Huang, T.J., Liaw, Y.C.: A fast k-means clustering algorithm using cluster center displacement. Pattern Recognit. 42(11), 2551–2556 (2009)CrossRef
Metadata
Title
Emulation of high-performance correlation-based quantum clustering algorithm for two-dimensional data on FPGA
Authors
Talal Bonny
A. Haq
Publication date
01-06-2020
Publisher
Springer US
Published in
Quantum Information Processing / Issue 6/2020
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-020-02683-9

Other articles of this Issue 6/2020

Quantum Information Processing 6/2020 Go to the issue