Developing a Grover's quantum algorithm emulator on standalone FPGAs: optimization and implementation

Seonghyun Choi; Woojoo Lee; Seonghyun Choi; Woojoo Lee

doi:10.3934/math.20241493

AIMS Mathematics

2024, Volume 9, Issue 11: 30939-30971. doi: 10.3934/math.20241493

Previous Article Next Article

Research article Special Issues

Developing a Grover's quantum algorithm emulator on standalone FPGAs: optimization and implementation

Seonghyun Choi ,
Woojoo Lee ^,

Department of Intelligent Semiconductor Engineering, Chung-Ang University 84, Heukseok-ro, Dongjak-gu, Seoul 06974, Korea

Received: 29 July 2024 Revised: 23 October 2024 Accepted: 24 October 2024 Published: 30 October 2024
MSC : 68Q12, 65D17, 94C30

Quantum computing (QC) leverages superposition, entanglement, and parallelism to solve complex problems that are challenging for classical computing methods. The immense potential of QC has spurred explosive interest and research in both academia and industry. However, the practicality of QC based on large-scale quantum computers remains limited by issues of scalability and error correction. To bridge this gap, QC emulators utilizing classical computing resources have emerged, with modern implementations employing FPGAs for efficiency. Nevertheless, FPGA-based QC emulators face significant limitations, particularly in standalone implementations required for low-power, low-performance devices like IoT end nodes, embedded systems, and wearable devices, due to their substantial resource demands. This paper proposes optimization techniques to reduce resource requirements and enable standalone FPGA implementations of QC emulators. We specifically focused on Grover's algorithm, known for its excellent performance in searching unstructured databases. The proposed resource-saving optimization techniques allow for the emulation of the largest possible Grover's algorithm within the constrained resources of FPGAs. Using these optimization techniques, we developed a hardware accelerator for Grover's algorithm and integrated it with a RISC-V processor architecture. We completed a standalone Grover's algorithm-specific emulator operating on FPGAs, demonstrating significant performance enhancements and resource savings afforded by the proposed techniques.
- Quantum computing (QC),
- QC emulator,
- Grover's algorithm,
- system-on-Chip platform,
- FPGA prototyping,
- optimization,
- design automation
Citation: Seonghyun Choi, Woojoo Lee. Developing a Grover's quantum algorithm emulator on standalone FPGAs: optimization and implementation[J]. AIMS Mathematics, 2024, 9(11): 30939-30971. doi: 10.3934/math.20241493

Related Papers:

Abstract

Quantum computing (QC) leverages superposition, entanglement, and parallelism to solve complex problems that are challenging for classical computing methods. The immense potential of QC has spurred explosive interest and research in both academia and industry. However, the practicality of QC based on large-scale quantum computers remains limited by issues of scalability and error correction. To bridge this gap, QC emulators utilizing classical computing resources have emerged, with modern implementations employing FPGAs for efficiency. Nevertheless, FPGA-based QC emulators face significant limitations, particularly in standalone implementations required for low-power, low-performance devices like IoT end nodes, embedded systems, and wearable devices, due to their substantial resource demands. This paper proposes optimization techniques to reduce resource requirements and enable standalone FPGA implementations of QC emulators. We specifically focused on Grover's algorithm, known for its excellent performance in searching unstructured databases. The proposed resource-saving optimization techniques allow for the emulation of the largest possible Grover's algorithm within the constrained resources of FPGAs. Using these optimization techniques, we developed a hardware accelerator for Grover's algorithm and integrated it with a RISC-V processor architecture. We completed a standalone Grover's algorithm-specific emulator operating on FPGAs, demonstrating significant performance enhancements and resource savings afforded by the proposed techniques.

References

[1]	T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, J. L. O'Brien, Quantum computers, Nature, 464 (2010), 45–53. https://doi.org/10.1038/nature08812
[2]	Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. V. Den Berg, S. Rosenblatt, et al., Evidence for the utility of quantum computing before fault tolerance, Nature, 618 (2023), 500–505. https://doi.org/10.1038/s41586-023-06096-3 doi: 10.1038/s41586-023-06096-3
[3]	Y. Kikuchi, C. McKeever, L. Coopmans, M. Lubasch, M, Benedetti, Realization of quantum signal processing on a noisy quantum computer, npj Quantum Inf., 9 (2023), 93. https://doi.org/10.1038/s41534-023-00762-0 doi: 10.1038/s41534-023-00762-0
[4]	Developing a Topological Qubit, Microsoft Azure Quantum Team, 2018. Available from: https://cloudblogs.microsoft.com/quantum/2018/09/06/developing-a-topological-qubit.
[5]	Google AI Quantum, Hartree-fock on a superconducting qubit quantum computer, Science, 369 (2020), 1084–1089. https://doi.org/10.1126/science.abb9811 doi: 10.1126/science.abb9811
[6]	C. G. Almudever, L. Lao, R. Wille, G. G. Guerreschi, Realizing quantum algorithms on real quantum computing devices, In: Design, Automation & Test in Europe Conference & Exhibition (DATE), 2020,864–872. https://doi.org/10.23919/DATE48585.2020.9116240
[7]	W. Alosaimi, A. Alharbi, H. Alyami, B. Alouffi, A. Almulihi, M. Nadeem, et al., Analyzing the impact of quantum computing on IoT security using computational based data analytics techniques, AIMS Math., 9 (2024), 7017–7039. https://doi.org/10.3934/math.2024342 doi: 10.3934/math.2024342
[8]	F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, et al., Quantum supremacy using a programmable superconducting processor, Nature, 574 (2019), 505–510. https://doi.org/10.1038/s41586-019-1666-5 doi: 10.1038/s41586-019-1666-5
[9]	S. McArdle, A. Gilyén, M. Berta, A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits, preprint paper, 2022. https://doi.org/10.48550/arXiv.2209.12887
[10]	G. Zhu, T. Jochym-O'Connor, A. Dua, Topological order, quantum codes, and quantum computation on fractal geometries, PRX Quantum, 3 (2022), 030338. https://doi.org/10.1103/PRXQuantum.3.030338 doi: 10.1103/PRXQuantum.3.030338
[11]	A. Silva, O. G. Zabaleta, FPGA quantum computing emulator using high level design tools, In: Eight Argentine Symposium and Conference on Embedded Systems (CASE), 2017. https://doi.org/10.23919/SASE-CASE.2017.8115369
[12]	E. El-Araby, N. Mahmud, M. J. Jeng, A. MacGillivray, M. Chaudhary, M. A. I. Nobel, et al., Towards complete and scalable emulation of quantum algorithms on high-performance reconfigurable computers, IEEE Transact. Comput., 72 (2023), 2350–2364. https://doi.org/10.1109/TC.2023.3248276 doi: 10.1109/TC.2023.3248276
[13]	C. F. Chen, A. M. Dalzell, M. Berta, F. G. S. L. Brandão, A. T. Joel, Sparse random Hamiltonians are quantumly easy, Phys. Rev. X, 14 (2024), 011014. https://doi.org/10.1103/PhysRevX.14.011014 doi: 10.1103/PhysRevX.14.011014
[14]	I. M. Hezam, O. Abdul-Raof, A. Foul, F. Aqlan, A quantum-inspired sperm motility algorithm, AIMS Math., 7 (2022), 9057–9088. https://doi.org/10.3934/math.2022504 doi: 10.3934/math.2022504
[15]	H. Li, Y. Pang, FPGA-accelerated quantum computing emulation and quantum key distillation, IEEE Micro, 41 (2021), 49–57. https://doi.org/10.1109/MM.2021.3085431 doi: 10.1109/MM.2021.3085431
[16]	H. S. Li, P. Fan, H. Xia, S. Song, X. He, The multi-level and multi-dimensional quantum wavelet packet transforms, Sci. Rep., 8 (2018), 13884. https://doi.org/10.1038/s41598-018-32348-8 doi: 10.1038/s41598-018-32348-8
[17]	J. M. Arrazola, V. Bergholm, K. Brádler, T. R. Bromley, M. J. Collins, I. Dhand, et al., Quantum circuits with many photons on a programmable nanophotonic chip, Nature, 591 (2021), 54–60. https://doi.org/10.1038/s41586-021-03202-1 doi: 10.1038/s41586-021-03202-1
[18]	J. Pilch, J. Długopolski, An FPGA-based real quantum computer emulator, J. Comput. Elect., 18 (2019), 329–342. https://doi.org/10.1007/s10825-018-1287-5 doi: 10.1007/s10825-018-1287-5
[19]	H. Shang, Y. Fan, L. Shen, C. Guo, J. Liu, X. Duan, et al., Towards practical and massively parallel quantum computing emulation for quantum chemistry, npj Quantum Inf., 9 (2023), 33. https://doi.org/10.1038/s41534-023-00696-7 doi: 10.1038/s41534-023-00696-7
[20]	Q. L. Kao, C. R. Lee, Preliminary performance evaluations of the determinant quantum Monte Carlo simulations for multi-core CPU and many-core GPU, Int. J. Comput. Sci. Eng., 9 (2014), 34–43. https://doi.org/10.1504/IJCSE.2014.058695 doi: 10.1504/IJCSE.2014.058695
[21]	L. K. Grover, A fast quantum mechanical algorithm for database search, In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996,212–219.
[22]	C. Zalka, Grover's quantum searching algorithm is optimal, Phys. Rev. A, 60 (1999), 2746. https://doi.org/10.1103/PhysRevA.60.2746 doi: 10.1103/PhysRevA.60.2746
[23]	A. Mandviwalla, K. Ohshiro, B. Ji, Implementing Grover's algorithm on the IBM quantum computers, In: IEEE International Conference on Big Data, 2018, 2531–2537. https://doi.org/10.1109/BigData.2018.8622457
[24]	S. Boettcher, S. Li, T. D. Fernandes, R. Portugal, Complexity bounds on quantum search algorithms in finite-dimensional networks, Phys. Rev. A, 98 (2018), 012320. https://doi.org/10.1103/PhysRevA.98.012320 doi: 10.1103/PhysRevA.98.012320
[25]	D. Qiu, L. Luo, L. Xiao, Distributed Grover's algorithm, Theoret. Comput. Sci., 993 (2024), 114461. https://doi.org/10.1016/j.tcs.2024.114461 doi: 10.1016/j.tcs.2024.114461
[26]	J. R. Jiang, Y. J. Wang, Quantum circuit based on Grover's algorithm to solve exact cover problem, In: VTS Asia Pacific Wireless Communications Symposium (APWCS), 2023. https://doi.org/10.1109/APWCS60142.2023.10234054
[27]	J. R. Jiang, T. H. Kao, Solving Hamiltonian cycle problem with Grover's algorithm using novel quantum circuit designs, In: IEEE 5th Eurasia Conference on IOT, Communication and Engineering (ECICE), 2023,796–801. https://doi.org/10.1109/ECICE59523.2023.10383125
[28]	M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, 10 Eds., Cambridge: Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667
[29]	L. M. Ionescu, A. G. Mazare, G. Serban, L. Ioan, D. Visan, A solution to implement Grover quantum computation algorithm using the binary representation of the phase on the FPGA, In: 11th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), 2019. https://doi.org/10.1109/ECAI46879.2019.9042138
[30]	S. Du, Y. Yan, Y. Ma, Quantum-accelerated fractal image compression: an interdisciplinary approach, IEEE Signal Proc. Lett., 22 (2014), 499–503. https://doi.org/10.1109/LSP.2014.2363689 doi: 10.1109/LSP.2014.2363689
[31]	K. Bag, M. Goswami, K. Kandpal, FPGA based resource efficient simulation and emulation Of Grover's search algorithm, In: IEEE 19th India Council International Conference (INDICON), 2022. https://doi.org/10.1109/INDICON56171.2022.10040039
[32]	ORCA Core, Vectorblox, 2024. Available from: https://github.com/riscveval/orca-1.
[33]	K. Han, S. Lee, J. J. Lee, W. Lee, M. Prdram, TIP: A temperature effect inversion-aware ultra-low power system-on-chip platform, In: IEEE/ACM International Symposium on Low Power Electronics and Design (ISLPED), 2019. https://doi.org/10.1109/ISLPED.2019.8824925
[34]	K. Han, S. Lee, K. I. Oh, Y. Bae, H. Jang, J. J. Lee, et al., Developing TEI-aware ultralow-power SoC platforms for IoT end nodes, IEEE Int. Things J., 8 (2021), 4642–4656. https://doi.org/10.1109/JIOT.2020.3027479 doi: 10.1109/JIOT.2020.3027479
[35]	E. Choi, J. Park, K. Lee, J. J Lee, K. Han, W. Lee, Day-Night architecture: Development of an ultra-low power RISC-V processor for wearable anomaly detection, J. Syst. Architect., 152 (2024), 103161. https://doi.org/10.1016/j.sysarc.2024.103161 doi: 10.1016/j.sysarc.2024.103161
[36]	J. Park, K. Han, E. Choi, J. J. Lee, K. Lee, W. Lee, et al., Designing low-power RISC-V multicore processors with a shared lightweight floating point unit for IoT endnodes, IEEE Transact. Circ. Syst. I: Regular Papers, 9 (2024), 4106–4119. https://doi.org/10.1109/TCSI.2024.3427681 doi: 10.1109/TCSI.2024.3427681
[37]	S. Jeon, H. Kwak, W. Lee, A study of advancing ultralow-power 3D integrated circuits with TEI-LP technology and AI-enhanced PID autotuning, Mathematics, 12 (2024), 543. https://doi.org/10.3390/math12040543 doi: 10.3390/math12040543
[38]	K. Lee, S. Jeon, K. Lee, W. Lee, M. Pedram, Radar-PIM: developing IoT processors utilizing processing-in-memory architecture for ultra-wideband radar-based respiration detection, IEEE Int. Things J., 2024. https://doi.org/10.1109/JIOT.2024.3466228
[39]	K. Han, H. Kwak, K. I. Oh, S. Lee, H. Jang, J. J. Lee, et al., STARC: crafting low-power mixed-signal neuromorphic processors by bridging SNN frameworks and analog designs, In: ACM/IEEE International Symposium on Low Power Electronics and Design (ISLPED '24), 2024. https://doi.org/10.1145/3665314.3670803
[40]	Ultrascale+, Xilinx, 2024. Available from: https://www.xilinx.com/products/silicon-devices/fpga/kintex-ultrascale-plus.html.
[41]	Arty-A7, Digilent, 2024. Available from: https://digilent.com/shop/arty-a7-artix-7-fpga-development-board/.
[42]	A. Kelly, Simulating quantum computers using OpenCL, preprint paper, 2018. https://doi.org/10.48550/arXiv.1805.00988
[43]	Vivado, Xilinx, 2024. Available from: https://www.amd.com/ko/products/software/adaptive-socs-and-fpgas/vivado.html.

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)