Skip to content
Back to the collection

Factoring integers with sublinear resources on a superconducting quantum processor

Bao Yan, Ziqi Tan, Shijie Wei

Show all 24 authors

Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, Yangyang Fei, Xiangdong Meng, Yu Han, Zheng Shan, Jiachen Chen, Xuhao Zhu, Chuanyu Zhang, Feitong Jin, Hekang Li, Chao Song, Zhen Wang, Zhi Ma, H. Wang, Gui-Lu Long

2022 · arXiv

Read the paper
HN score
0
Mentions
3
Readers
3
Months
3
What’s in a score?

From the abstract

Shor's algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, 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/loglog N), 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

3 selected excerpts · 3 total mentions

vlovich123
Neutral mention · rule
The involvement of the quantum computer is only that it's an adversary that can break asymmetric encryption with different complexity constraints than a classical computer. For example, take two random prime numbers as a secret and publish the result of multiplying them. It turns out that if you want to find the two random prime numbers by knowing only the result of multiplication is a hard problem known as integer factorization. If you double the size of the prime numbers, discovering them takes exponentially longer. The theoretical quantum computer model though says that it can accomplish it in sub-exponential time. Now doubling the size of the number only increases…
Read the full comment
your compute requirements by ~2x to recover the prime factors (specifically it's actually a logarithm so it's < 2x more compute is needed). The algorithm for doing this is known as Shor's algorithm [0] and because of how complexity works in computer science, it turns out that this algorithm can be applied to many many problems mechanically and these problems are the underpinnings of RSA, DSA, ECDH key exchanges. These quantum-resistant algorithms are based on mathematical problems believed to be exponentially difficult even for a theoretical quantum computer - when you double the size of the problem, it again takes exponentially more time even for a theoretical quantum computer. These are of course unproven beliefs but that's true of classical algorithms too. So no, it doesn't matter where you run the cryptographic algorithm; it remains computationally difficult to solve the problem without knowing the secret. The quantum computer is critically important though for your ability to crack classical problems though - without it, all of this post-quantum cryptography is unnecessary. [0] https://en.wikipedia.org/wiki/Shor%27s_algorithm [1] https://arxiv.org/pdf/2212.12372
0xpino
Neutral mention · rule
Secure private data from your deepest secrets. As a cybersecurity researcher, I have noticed a great lack of innovation in encryption algorithms in more than two decades. But in January 2023, an event changed everything, after Chinese researchers managed to crack the 2048-bit RSA algorithm with just 372 qubits. This fact highlights the urgent need to evolve our cryptography against the power of quantum computing. Source: https://arxiv.org/pdf/2212.12372.pdf After learning about the above, being inspired by Moore's Law and the concept of #bitcoin halving, I envisioned a future with crypto that would adapt over time. Thus was born temcrypt, designed to protect highly…
Read the full comment
sensitive data. Create a Scalable Complexity Factor incorporating 18-month cycles to increase the complexity of temcrypt and a custom clock that advances and adds one hour every 6 months. The dependency to decrypt the data is based on a unique key, the time it was encrypted, and the processing power of your machine. If you don't apply the exact key at the exact time (hour and minute) in later days, decrypting the information becomes “impossible”. You can read more in the following repository paths: ▪ Readme: https://github.com/jofpin/temcrypt/blob/main/README.md ▪ Knowledge: https://github.com/jofpin/temcrypt/blob/main/KNOWLEDGE.md With temcrypt, you can have many use cases. Some I can mention include protection for your seed phrases (cryptocurrency wallets), business data, military data, medical data, and much more. I hope you enjoy temcrypt and share it with your friends, coworkers, developers, lawyers, journalists, and people around the world who deserve to protect their most sensitive data. This is a big step for a new era of new ways to encrypt and protect data. Follow me on: https://twitter.com/jofpin
Strilanc
Neutral mention · rule
I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least…
Read the full comment
this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2]. The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by hoping potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA". How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them. Is there somewhere where I can bet money that this doesn't amount to anything? 1: https://arxiv.org/abs/quant-ph/9508027 2: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2... 3: https://arxiv.org/abs/2212.12372

Keep following the thread.

More in Physics

More from the same topics.