What is Quantum Computing?
The International Patent Classification (IPC)1 includes a category related to quantum computing titled: "G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena".
The quantum-mechanical phenomena that make a computer a quantum computer are "qubits".
Qubits are quantum analogues of a classical bit (a qubit is a quantum bit)2. In classical computers information is encoded in bits which can have values of zero or one. Qubits have two basis states of 0 and 1, but, using the principle of superposition, qubits can also be in a state which is a linear combination of the two basis states. It is it this quantum principle of superposition that differentiates a qubit from a bit.
A group of qubits can also become entangled, where the quantum state of each particle cannot be described independently of the other particles3. The fact that qubits can be entangled, and that the information is stored in a superposition, means that quantum computers can solve some problems much faster than classical computers.
The Integer Factorization Problem
An example of a problem that a quantum computer can solve faster than a classical computer is the integer factorization problem.
The problem is as follows: given a number N, find the two prime integers, P and Q, that multiply together to give N.
If N is small, then the problem is trivial. For instance, if N = 6, it would be simple for either a human or a computer to determine that P and Q are 2 and 3. However, it is more difficult to determine that the prime factors of N = 1,034,776,851,837,418,228,051,242,693,253,376,923 are P = 1,086,027,579,223,696,553 and Q = 952,809,000,096,560,2914. Hence, the difficulty of the problem increases the larger the value of N.
Why is this problem significant? Because the integer factorization problem is used as the basis for some of the cryptosystems that are used to protect information online, such as RSA encryption.
RSA Encryption
RSA is a commonly used encryption system that is based on the integer factorization problem5.
A person, Alice, owns a pair of keys consisting of a public key and a corresponding private key. Alice can openly distribute the public key to another person, Bob, without compromising security. However, Alice must keep the private key secret.
Bob can use Alice's public key to encrypt a message, which yields a ciphertext. Only the people who know the corresponding private key (which in this case is only Alice) can decrypt the ciphertext to obtain the original message.
Hence, the public key is used to encrypt data and the private key is used to decrypt encrypted data.
RSA can be used to complement the one-time pad technique, a technique which involves Alice and Bob using a shared key to both encrypt and decrypt messages they send to each other6. A one-time pad is secure against any attacking computer with any computing power. However, this security is dependent on the shared key being distributed secretly between Alice and Bob, otherwise an eavesdropper may obtain the shared key and use it to decrypt any further messages sent between Alice and Bob.
Bob can use RSA to send the shared key to Alice. Further correspondence between Alice and Bob can then be conducted via the one-time pad technique, using the shared key to which they now both have access.
In RSA, the integer N is a part of the public key and the corresponding prime integers, P and Q, are a part of the private key.
Therefore, the security of a message from Bob to Alice is dependent upon a third party, which knows of the public key, being unable to determine the private key. Hence, the security is dependent upon a third party, which knows the value of N, being unable to determine the prime integers P and Q, or, in other words, being unable to solve the integer factorization problem.
No algorithm has yet been determined that can be run on a classical computer to efficiently find the prime factors of a large number (although that does not mean that such an algorithm could not be found in the future). Therefore, cryptosystems such as RSA are thought to be relatively secure against classical computers.
However, the development of quantum computing may pose a threat to these cryptosystems.
Quantum Computers v Classical Cryptography
Shor's algorithm
In 1994, Peter Shor developed an algorithm for a quantum computer that allowed it to find the prime factors of an integer in polynomial time (which is an efficient time for a computer to solve this problem). Shor's algorithm achieves this by utilising the quantum properties that are unique to qubits – quantum superposition and interference.
The ability of a quantum computer to solve the integer factorization problem was experimentally demonstrated in 2001, when IBM researchers used a quantum computer comprising 7 qubits to factor the number 157.
Clearly 15 is a much smaller number than the ones used for RSA, which typically have standard key sizes comprising 2048 to 4096 bits. However, if 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 RSA encryption.
Qubit size of quantum computers
In December 2023, IBM unveiled their largest-ever quantum computer, Condor, which comprises over 1000 qubits8.
One estimate for the number of qubits a quantum computer would require to factor 2048-bit RSA keys is 20 million qubits, and such a quantum computer would take eight hours to complete the calculation9.
Therefore, as the sizes of quantum computers increase, and hence the threat to encryption based on hard mathematical problems grows, there is interest in the development of alternative techniques which do not rely on the integer factorization problem for security.
One alternative technique is to fight (quantum) fire with (quantum) fire, and so use quantum phenomena to offer a potential solution in the form of 'quantum cryptography', which we discuss in a future article.
Footnotes
1. The International Patent Classification (IPC) can be accessed at: https://www.wipo.int/classifications/ipc/en/
2. What is a qubit? (quantum-inspire.com)
3. What is Quantum Computing? | IBM
5. Rivest, R.; Shamir, A.; Adleman, L. (February 1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM. 21(2): 120–126
6. Lugrin, Thomas (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent; Tellenbach, Bernhard (eds.), "One-Time Pad", Trends in Data Protection and Encryption Technologies, Cham: Springer Nature Switzerland, pp. 3–6
7. Vandersypen, L., Steffen, M., Breyta, G. et al. Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature414, 883–887 (2001)
8. IBM's 'Condor' quantum computer has more than 1000 qubits | New Scientist
9. RSA's demise from quantum attacks is very much exaggerated, expert says | Ars Technica
The content of this article is intended to provide a general guide to the subject matter. Specialist advice should be sought about your specific circumstances.
