nach oben

Quantum Information Processing

Erschienen in:

01.06.2020

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

verfasst von: Talal Bonny, A. Haq

Erschienen in: Quantum Information Processing | Ausgabe 6/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Fidelity of quantum teleportation in correlated quantum channels

Nächster Artikel Resolution map in quantum computing: signal representation by periodic patterns

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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)

Chen, J., Zhang, L., Liang, Y.: Full-duplex transceiver design: a GMM clustering approach. In: 2018 IEEE International Conference on Communication Systems (ICCS), Chengdu, China, 2018, pp. 433–438. https://doi.org/10.1109/iccs.2018.8689230

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)

Bifet, A.: Machine Learning for Data Streams, Chapter 9. MIT Press, Cambridge (2018)CrossRef

Oshurko, I.: Quantum Machine Learning. Quantum Information and Computation Course (2016). https://pdfs.semanticscholar.org/776b/5c7b2966fd700980361aa32ee573edb70bf3.pdf

Benioff, P.: Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys. 29, 515–546 (1982). https://doi.org/10.1007/BF01342185 ADSMathSciNetCrossRefMATH

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

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

Xin, T.: A novel approach for emulating quantum computers on classical platforms. Quantum Eng 1(2), e18 (2019)CrossRef

10.

Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54(1), 147 (1996)ADSMathSciNetCrossRef

11.

Van Meter, R., Itoh, K.M.: Fast quantum modular exponentiation. Phys. Rev. A 71(5), 052320 (2005)ADSMathSciNetCrossRef

12.

Pilch, J., Długopolski, J.: An FPGA-based real quantum computer emulator. J. Comput. Electron. 18(1), 329–342 (2019)CrossRef

13.

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.

Hu, F., Wang, B.N., Wang, N., et al.: Quantum machine learning with D-wave quantum computer. Quantum Eng. 1(2), e12 (2019)

15.

Britt, B.C.: Modeling viral diffusion using quantum computational network simulation. Quantum Eng. 2(1), e29 (2020)CrossRef

16.

Wang, S.H., Long, G.L.: Big data and quantum computation. Chin. Sci. Bull. 60(5–6), 499–508 (2015)CrossRef

17.

Coughlin, T: 175 zetabytes by 2025. Forbes (2018). https://www.forbes.com/sites/tomcoughlin/2018/11/27/175-zettabytes-by-2025/#283740d54597

18.

Aïmeur, E., Brassard, G., Gambs, S.: Quantum clustering algorithms. In: Proceedings of the 24th International Conference on Machine Learning, pp. 1–8 (2007). http://dx.doi.org/10.1145/1273496.1273497

19.

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)

20.

Long, G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A 64(2), 022307 (2001)ADSMathSciNetCrossRef

21.

Tsai, C., Liao, Y., Chiang, M.: A quantum-inspired evolutionary clustering algorithm. In: 2013 International Conference on Fuzzy Theory and Its Applications (iFUZZY), Taipei, 2013, pp. 305–310. https://doi.org/10.1109/ifuzzy.2013.6825455

22.

Han, K.-H., Kim, J.-H.: A quantum-inspired evolutionary algorithm for a class of combinatorial optimization. Trans. Evol. Comput. 6, 580–593 (2002). https://doi.org/10.1109/TEVC.2002.804320 MathSciNetCrossRef

23.

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.

MATLAB, 2017. an 9.3 (R2017b), Natick, Massachusetts: The MathWorks Inc

25.

Vivado. 2018.2. The Xilinx, Inc. https://www.xilinx.com/products/design-tools/vivado.html

26.

Zedboard. Xilinx, Inc. https://www.xilinx.com/products/boards-and-kits/1-8dyf-11.html

27.

Fränti, P., Sieranoja, S.: K-means properties on six clustering benchmark datasets. Appl. Intell. 48(12), 4743–4759 (2018). https://doi.org/10.1007/s10489-018-1238-7 CrossRefMATH

28.

Jin, X., Han, J.: K-means clustering. In: Sammut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning. Springer, Boston (2011)

29.

Arthur, D., Vassilvitskii, S.: K-means++: the advantages of careful seeding. In: 19th SODA (2007), pp. 1027–1035

30.

Malinen, M.I., Mariescu-Istodor, R., Fränti, P.: K-means*: clustering by gradual data transformation. Pattern Recognit. 47, 3376–3386 (2014)CrossRef

31.

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

Titel: Emulation of high-performance correlation-based quantum clustering algorithm for two-dimensional data on FPGA
verfasst von: Talal Bonny
A. Haq
Publikationsdatum: 01.06.2020
Verlag: Springer US
Erschienen in: Quantum Information Processing / Ausgabe 6/2020
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-020-02683-9

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Nachhaltigkeitsaward Key Visual/© Cometis AG/Global ESG Monitor | Daniel Rupp | Generiert mit KI, Search Icon, Banner Hanser, Barbara Liebermeister/© Barbara Liebermeister, Jonas Klose/© Pine Valley Capital GmbH, Carina Kießling von der Strategieberatung Roland Berger/© Monika Walther Fotografie | ATZ, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2020

Semi-quantum private comparison based on Bell states

Majorana fermions induced Fano resonance and fast-to-slow light in a hybrid semiconductor/superconductor ring device

Separability of heterogeneous multipartite quantum systems using Bloch Vectors

Solving diner’s dilemma game, circuit implementation and verification on the IBM quantum simulator

Quantum circuit design of approximate median filtering with noise tolerance threshold

Quantum algorithms for typical hard problems: a perspective of cryptanalysis

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.