The quantum computer has a potential to reduce computation time compared to classical ones for certain problems. Typical example of the problem is the prime factorization. Shor's algorithm is widely recognized to solve the prime factorization effectively [1]. However, to implement this algorithm in the gate-type quantum computer requires the large numbers of qubits with sufficient fidelity. Another candidate method uses quantum annealing (QA), where the prime factorization is treated as an optimization problem with solutions as the global minimum of the Hamiltonian [2]. In this method, classical computation is required to calculate the Gröbner basis, which helps to reduce the cost function. We have investigated an alternative method that can solve the prime factorization by QA directly. In our method, the superconducting quantum circuit with a function of the Multiplier unit (MU) is utilized [3,4]. The circuit of MU performs factorization of two digits in binary. Using the connection qubit (CQ), carry transfer is possible between MUs [5]. With a combination of the MUs and CQs, it is expected that a highly scalable quantum circuit can be created. In this work, we demonstrate the 4-bit factorization circuit composed of 4-MUs. The quantum annealing circuit is fabricated by using a process that creates four Nb layers and a Josephson junction with a critical current density of 1 μA/μm2. In the device design and analysis of its performance, a Josephson integrated circuit simulation (JSIM) was utilized [6]. Experiment was carried out both at 4.2-K and 10-mK. The qubits used in this experiment are superconducting compound Josephson junction rf-SQUID flux qubits[3,4].
The MUij (i = 0-1, j = 0-1) is composed of 6-superconducting flux qubits with all-to-all connectivity. Six qubits (Xij, Yij, Zij, Dij, Cij, Sij) correspond to the Xij and Yij for inputs, Zijfor sum-in, Dij for carry-in, Cij for carry-out, and Sij for summation. To accomplish the carry transfer between MUs, 8-CQs are utilized. An inductance of each CQ was designed so that it would not fail in carry transfer. Our 4-bit factorization circuit is consisted by 32-superconducting flux qubits. Input (X, Y) and output (P) relationship is expressed by X = X01X00, Y = Y11Y01 and P = C11S11S10S00 (binary notation). The JSIM analysis was carried out with 100 iterations in order to estimate a success probability of the factorization. Solutions of (10)2×(10)2 and (11)2×(11)2 were successfully obtained in cases of the annealing with P = (0100)2 and P = (1001)2, respectively. In the annealing with P = (0110)2, solutions of (10)2×(11)2 and (11)2×(10)2 were clearly obtained. Similar combinations of X and Y were also confirmed in the experiment.
Acknowledgements
This work is partly funded by the NEC-AIST Quantum Technology Cooperative Research Laboratory. This work is partly based on results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO), Japan (project number JPNP16007). The devices were fabricated in the clean room for analog-digital superconductivity (CRAVITY) in National Institute of Advanced Industrial Science and Technology (AIST).
References
[1] Shor, W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484-1509 (1997).
[2] Dridi, R. & Alghassi, H. Prime factorization using quantum annealing and computational algebraic geometry. Sci. Rep. 7, 43048 (2017).
[3] Saida, D. et al. Experimental demonstrations of native implementation of Boolean logic Hamiltonian in a superconducting quantum annealer. IEEE Trans. Quant. Eng. 2, 3103508-3103515 (2021).
[4] Saida, D. et al. Factorization by quantum annealing using superconducting flux qubits implementing a multiplier Hamiltonian. Sci. Rep. 12, 13669 (2022).
[5] Saida D. et al, Quantum annealing with native implementation of Hamiltonian in the multiplier unit, ISS2021, ED7-6.
[6] Fang, E. S., & Van Duzer, T., A Josephson Integrated Circuit Simulator (JSIM) for superconductive electronics application. in Proc. Ext. Abstr. 2nd Int. Supercond. Electron. Conf., 407 (1989).
Keywords: quantum computer, quantum annealing, superconducting flux qubit, prime factorization