Global computer and chip manufacturer Fujitsu today reported that a new study performed on its 39-qubit quantum simulator suggests it will remain difficult for quantum computers to crack RSA cryptography for years to come. The announcement came as a prelude to Fujitsu’s formal presentation of study results at the 2023 Symposium on Cryptography and Information Security (SCIS 2023) being held in Kitakyushu, Japan, this week.

Working with a version of Shor’s algorithm, Fujitsu researchers reported that a fault-tolerant quantum computer with a scale of approximately 10,000 qubits and 2.23 trillion quantum gates would be required to crack RSA – vastly beyond the most advanced quantum computers in the world today. Researchers further estimated that it would be necessary to conduct fault-tolerant quantum computation for about 104 days to successfully crack RSA.

“Our research demonstrates that quantum computing doesn’t pose an immediate threat to existing cryptographic methods. We cannot be complacent either, however. The world needs to begin preparing now for the possibility that one day quantum computers could fundamentally transform the way we think about security,” said Tetsuya Izu, senior director of data and security research at Fujitsu.

Fujitsu is quickly emerging as a substantial player in quantum technology.

• It recently announced plans to develop and deploy a 64-qubit quantum computer with Riken in 2023. The new quantum computer will be based on semiconductor-based superconducting qubits – similar to approaches by other such as IBM, Rigetti, and Google. Few details about the new computer have been disclosed so far.
• The company launched its quantum simulator in 2022 and plans to boost its capacity to 40 qubits in Q1 2023. In 2018 Fujitsu launched a digital annealer service, “Using a digital circuit design inspired by quantum phenomena, the digital annealer focuses on rapidly solving complex combinatorial optimization problems without the added complications and costs typically associated with quantum computing methods.” Last fall, Fujitsu struck a deal with Toyota to leverage is digital annealer in auto production applications.
• In November, Fujitsu announced development of quantum/HPC hybrid computing technology to optimize workload selection for customers. “The new AI-based software, which serves as a precursor to a future computer workload broker technology, automatically selects from different next-generation computing platforms to offer the optimal solution to customers’ problems based on parameters including calculation time, calculation accuracy, and costs.”

The latest work investigating Shor’s algorithm was performed on Fujitsu’s quantum simulator; that system leverages technology developed for Japan’s Fugaku supercomputer (number two on the latest Top500 List) and specialized qubit-handling technology: “Using a cluster system based on Fujitsu’s 512 node supercomputer PRIMEHPC FX700 hardware, which features the A64FX CPU, and a newly developed technology that automatically and efficiently rearranges the state information of quantum bits, Fujitsu achieved a speed increase of more than 100 times that of a system without rearrangement in 64 nodes, and was able to perform factoring of N = 253 in 463 seconds, which previously took 16 hours,” reported Fujitsu. More details about the simulation are presented at the end of the article.

Predictably, developing measures to prevent quantum computers from breaking modern encryption methods – most notably RSA – is an area of vigorous research and hot debate within the quantum community. Not everyone thinks the threat is as distant Fujitsu reports. Qubits-counts worldwide are climbing quickly. IBM debuted a 443-qubit QPU late last year and plans a 1,100-qubit system in 2023.

It’s now taken as a given that when sufficiently large fault-tolerant quantum computers become available, Shor’s algorithm will be able to quickly decrypt today’s factoring-based encryption schemes, including RSA. Last summer the National Institute of Technology and Standards (NIST), released its first set of new algorithms to replace current RSA methods. (See HPCwire coverage, The Race to Ensure Post Quantum Data Security). Many warn that bad actors are now engaged in so-called Store Now/Decrypt Later strategies.

There is swirling debate around how soon NISQ (noisy intermediate scale quantum) computers or non-gate-based quantum annealing approaches will be able to decrypt RSA data.

In a December ’22 paper, researchers from China reported a breakthrough in developing a method able to decrypt RSA-2048 that would require only 372 qubits.

They wrote, “ [We] report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglogN), which is sublinear in the bit length of the integer N, making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.”

Events are moving quickly and there are other reports of decryption advances using both gate-based quantum computers and quantum annealing computers with the factorization problem reformulated as an optimization task.

Stay tuned.

Fujitsu Description of Quantum Study (excerpt)

“Within the trials, Fujitsu implemented a general-purpose program using Shor’s algorithm on a quantum simulator to generate a quantum circuit that factors the input composite number into prime factors. As a result, Fujitsu succeeded in factoring 96 RSA-type integers (a product of two different odd primes) from N = 15 to N = 511, and confirmed that the general-purpose program can generate correct quantum circuits.

“By using the above general purpose program, Fujitsu further generated quantum circuits that factor several composite numbers from 10 bits to 25 bits, and estimated the required resources of the quantum circuits necessary for factoring 2,048 bits composite numbers from the calculated resources. As a result, Fujitsu found that approximately 10,000 qubits, 2.23 trillion quantum gates, and a quantum circuit with a depth (6) of 1.80 trillion were required to factor a composite number of 2,048 bits. This equates to a 104-day long calculation using a fault-tolerant quantum computer. As a quantum computer that can operate stably and at such a large scale will not be realized in the short term, Fujitsu’s tests quantitatively proved that the RSA cryptosystem is safe against the Shor’s algorithm for the time being.

“Within the trials, Fujitsu utilized its quantum simulator leveraging the high-speed computing power of the CPU “A64FX” of the supercomputer “Fugaku” and Fujitsu’s massively parallel computing technology. Using a cluster system based on Fujitsu’s 512 node supercomputer “FUJITSU Supercomputer PRIMEHPC FX700” hardware, which features the A64FX CPU, and a newly developed technology that automatically and efficiently rearranges the state information of quantum bits, Fujitsu achieved a speed increase of more than 100 times that of a system without rearrangement in 64 nodes, and was able to perform factoring of N = 253 in 463 seconds, which previously took 16 hours.”