{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:41:02Z","timestamp":1752230462613},"reference-count":24,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T00:00:00Z","timestamp":1728518400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"crossref","award":["24DP2600100"],"award-info":[{"award-number":["24DP2600100"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"crossref","award":["22TQ017"],"award-info":[{"award-number":["22TQ017"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12271109"],"award-info":[{"award-number":["12271109"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["71991471"],"award-info":[{"award-number":["71991471"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2020YFA0711902"],"award-info":[{"award-number":["2020YFA0711902"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shanghai Institute for Mathematics and Interdisciplinary Sciences","award":["SIMIS-ID-2024-(CN)"],"award-info":[{"award-number":["SIMIS-ID-2024-(CN)"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Nonlinear boolean equation systems play an important role in a wide range of applications. Grover&amp;apos;s algorithm is one of the best-known quantum search algorithms in solving the nonlinear boolean equation system on quantum computers. In this paper, we propose three novel techniques to improve the efficiency under Grover&amp;apos;s algorithm framework. A W-cycle circuit construction introduces a recursive idea to increase the solvable number of boolean equations given a fixed number of qubits. Then, a greedy compression technique is proposed to reduce the oracle circuit depth. Finally, a randomized Grover&amp;apos;s algorithm randomly chooses a subset of equations to form a random oracle every iteration, which further reduces the circuit depth and the number of ancilla qubits. Numerical results on boolean quadratic equations demonstrate the efficiency of the proposed techniques.<\/jats:p>","DOI":"10.22331\/q-2024-10-10-1500","type":"journal-article","created":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T11:04:47Z","timestamp":1728558287000},"page":"1500","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Resource Efficient Boolean Function Solver on Quantum Computer"],"prefix":"10.22331","volume":"8","author":[{"given":"Xiang","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Fudan University"}]},{"given":"Hanxiang","family":"Shen","sequence":"additional","affiliation":[{"name":"Shanghai Center for Mathematical Science, Fudan University"}]},{"given":"Weiguo","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Fudan University"},{"name":"Shanghai Key Laboratory for Contemporary Applied Mathematics"}]},{"given":"Yingzhou","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Fudan University"},{"name":"Shanghai Key Laboratory for Contemporary Applied Mathematics"}]}],"member":"9598","published-online":{"date-parts":[[2024,10,10]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574:505\u2013510, 2019. doi:10.1038\/s41586-019-1666-5.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"1","doi-asserted-by":"publisher","unstructured":"William P. Baritompa, David W. Bulger, and Graham R. Wood. Grover&apos;s quantum algorithm applied to global optimization. SIAM Journal on Optimization, 15(4):1170\u20131184, 2005. doi:10.1137\/040605072.","DOI":"10.1137\/040605072"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Jan Balewski, Daan Camps, Katherine Klymko, and Andrew Tritt. Efficient quantum counting and quantum content-addressable memory for dna similarity. pages 378\u2013384. IEEE, 9 2023. doi:10.1109\/QCE57702.2023.00050.","DOI":"10.1109\/QCE57702.2023.00050"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Peter Brucker and Andreas Kr\u00e4mer. Shop scheduling problems with multiprocessor tasks on dedicated processors. Annals of Operations Research, 57(1):13\u201327, 1995. doi:10.1007\/BF02099688.","DOI":"10.1007\/BF02099688"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Alex Brodsky. Reversible circuit realizations of boolean functions. In Jean-Jacques Levy, Ernst W. Mayr, and John C. Mitchell, editors, Exploring New Frontiers of Theoretical Informatics, pages 67\u201380, Boston, MA, 2004. Springer US. doi:10.1007\/1-4020-8141-3_8.","DOI":"10.1007\/1-4020-8141-3_8"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Yu-Ao Chen and Xiao-Shan Gao. Quantum algorithm for boolean equation solving and quantum algebraic attack on cryptosystems. Journal of Systems Science and Complexity, pages 1\u201340, 2022. doi:10.1007\/s11424-020-0028-6.","DOI":"10.1007\/s11424-020-0028-6"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Martin F\u00fcrer. Solving np-complete problems with quantum search. In Latin American Symposium on Theoretical Informatics, pages 784\u2013792. Springer, 2008. doi:10.1007\/978-3-540-78773-0_67.","DOI":"10.1007\/978-3-540-78773-0_67"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Ronald Lewis Graham, Eugene Leighton Lawler, Jan Karel Lenstra, and Alexander H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. In Annals of discrete mathematics, volume 5, pages 287\u2013326. Elsevier, 1979. doi:10.1016\/S0167-5060(08)70356-X.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt. Applying grover&apos;s algorithm to aes: quantum resource estimates. In International Workshop on Post-Quantum Cryptography, pages 29\u201343. Springer, 2016. doi:10.1007\/978-3-319-29360-8_3.","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Jovan Dj Goli\u0107. Fast low order approximation of cryptographic functions. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 268\u2013282. Springer, 1996. doi:10.1007\/3-540-68339-9_24.","DOI":"10.1007\/3-540-68339-9_24"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212\u2013219, 1996. doi:10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Kazuo Iwama, Yahiko Kambayashi, and Shigeru Yamashita. Transformation rules for designing cnot-based quantum circuits. In Proceedings of the 39th Annual Design Automation Conference, DAC &apos;02, pages 419\u2013424, New York, NY, USA, 2002. Association for Computing Machinery. doi:10.1145\/513918.514026.","DOI":"10.1145\/513918.514026"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Neal Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203\u2013209, 1987. doi:10.1090\/S0025-5718-1987-0866109-5.","DOI":"10.1090\/S0025-5718-1987-0866109-5"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Mitsuru Matsui. Linear cryptanalysis method for des cipher. In Workshop on the Theory and Application of of Cryptographic Techniques, pages 386\u2013397. Springer, 1993. doi:10.1007\/3-540-48285-7_33.","DOI":"10.1007\/3-540-48285-7_33"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Edward J. McCluskey. Minimization of boolean functions. The Bell System Technical Journal, 35(6):1417\u20131444, 1956. doi:10.1002\/j.1538-7305.1956.tb03835.x.","DOI":"10.1002\/j.1538-7305.1956.tb03835.x"},{"key":"15","unstructured":"Giovanni De Micheli. Synthesis and Optimization of Digital Circuits. McGraw-Hill Higher Education, 1994."},{"key":"16","doi-asserted-by":"publisher","unstructured":"William Millan. Low order approximation of cipher functions. In International Conference on Cryptography: Policy and Algorithms, pages 144\u2013155. Springer, 1995. doi:10.1007\/bfb0032354.","DOI":"10.1007\/bfb0032354"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. doi:10.1119\/1.1463744.","DOI":"10.1119\/1.1463744"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120\u2013126, 1978. doi:10.1145\/359340.359342.","DOI":"10.1145\/359340.359342"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303\u2013332, 1999. doi:10.1137\/S0097539795293172.","DOI":"10.1137\/S0097539795293172"},{"key":"20","doi-asserted-by":"publisher","unstructured":"V.V. Shende, A.K. Prasad, I.L. Markov, and J.P. Hayes. Synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(6):710\u2013722, 2003. doi:10.1109\/TCAD.2003.811448.","DOI":"10.1109\/TCAD.2003.811448"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Matthew Treinish, Jay Gambetta, Paul Nation, qiskit bot, Paul Kassebaum, Diego M. Rodr\u00edguez, Salvador de la Puente Gonz\u00e1lez, Shaohan Hu, Jake Lishman, Kevin Krsulich, Jim Garrison, Luciano Bello, Jessie Yu, Manoel Marques, Julien Gacon, David McKay, Juan Gomez, Lauren Capelluto, Travis-S-IBM, Ashish Panigrahi, lerongil, Rafey Iqbal Rahman, Steve Wood, Toshinari Itoko, Abby Mitchell, Alex Pozas-Kerstjens, Christopher J. Wood, Divyanshu Singh, Drew Risinger, and Eli Arbel. Qiskit\/qiskit: Qiskit 0.39.3, 2022. doi:10.5281\/ZENODO.7363289.","DOI":"10.5281\/ZENODO.7363289"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Ben Travaglione, M. Nielsen, Howard Wiseman, and Andris Ambainis. Rom-based computation: quantum versus classical, 2002. doi:10.26421\/QIC2.4-5.","DOI":"10.26421\/QIC2.4-5"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al. Strong quantum computational advantage using a superconducting quantum processor. Physical Review Letters, 127(18):180501, 2021. doi:10.1103\/PhysRevLett.127.180501.","DOI":"10.1103\/PhysRevLett.127.180501"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-10-10-1500\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T11:04:53Z","timestamp":1728558293000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-10-10-1500\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,10]]},"references-count":24,"URL":"https:\/\/doi.org\/10.22331\/q-2024-10-10-1500","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,10]]},"article-number":"1500"}}