@jvaleska.eth

so, are we scared of that? Assuming a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as The RSA scheme The finite-field Diffie–Hellman key exchange The elliptic-curve Diffie–Hellman key exchange[9] RSA can be broken if factoring large integers is computationally feasible. As far as is known, this is not possible using classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers can be done with a polynomial complexity circuit on an ideal quantum computer. Thus, it might be feasible to defeat RSA by constructing a large enough quantum computer. This was a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography (PQC). In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3×5, using an NMR implementation of a quantum computer with seven qubits.[10] After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running Shor's algorithm circuits.[11][12] In 2012, the factorization of 15 was performed with solid-state qubits.[13] Later, in 2012, the factorization of 21 was achieved.[14] In 2016, the factorization of 15 was performed again using trapped-ion qubits.[15] However, none of these demonstrations fulfill the requirements of Shor’s algorithm: they compile the circuit using prior knowledge of the solution, and some have even oversimplified the algorithm in a way that makes it equivalent to coin flipping.[16]

1 reply

1 recast

4 reactions