“I think there is a world market for maybe five computers” , a misquote attributed to Thomas J. Watson.
The title of this post is an adaptation of the misquote to quantum computing.
The title is particularly bizarre when viewed in the context of how unbelievable the misquoted prediction sounds now. Nevertheless, I fail to see, based on what is currently known, how future end users would benefit from owning a quantum computer. Some researchers believe that building quantum computers would be a revolution of the same scale as the print, and digital revolution. I believe that this is not the case, and the implications would be more subtle.
Before I begin, I want to stress: I’m all for quantum computation, I’m working on my PhD. in that field, and find it fascinating. My goal is not to bash quantum computing, but to point out issues known within the community studying this field, which are absent in popular science publications.
Two common questions are asked in popular science articles regarding quantum computers.
The first one is: in what aspects is a quantum computer better than a classical computer? The following article serves as an excellent starting point.
After realizing that quantum computation has several “killer apps”, the natural thing is to want to have one. Therefore, the next question is: What stops us from building a quantum computer? I don’t know any good popular science articles about this, but the following paper presents the current state of the art approaches to building a quantum computer.
I wish to focus on the gap between the fact that quantum computation has several “killer apps”, and the desire to own a quantum computer: what will the end user gain from owning a quantum computer? Currently, I cannot see how the end user will benefit. I believe quantum computers will only serve scientists and data centers; hence, the provocative title of this post.
Let’s imagine the following setting: In 50 years, there are quantum computers available. Let’s assume that quantum computers cost twice more than classical computers. Will the average 2060 grandpa be willing to spend twice as much for the added features?
I wish to discuss some of the known “killer apps” of quantum computers, and explain in what way they may serve the end users. If you’re an optimist, you may choose to go straight to the topic of solving linear equations.
Description: Alice and Bob want to talk with each other and keep their conversation private, even though the line they use is public (this is exactly the case when Wi-Fi is used, and everyone around can receive the bits transmitted over the air).
Classical computers can be used for encryption: when you surf to your bank’s website, a classical encryption scheme is used. If we have classical encryption schemes, why should we use quantum encryption schemes?
Alas, an answer to this question requires an explanation about how classical encryption works, and what assumptions are needed.
The first thing to note is that modern encryption is almost a miracle: Suppose Alice wants to send a message to Bob while keeping the conversation private. How can that be possible, when the conversation is public, without having met previously? (if they meet, they can use one time pad encryption). Modern cryptography uses the following observation: we don’t really care if a third party can theoretically eavesdrop to the conversation. If it takes a billion years (in terms of computational time) to understand the conversation, that’s fine too. In modern cryptography, the goal is to make it hard, in terms of computational time, to decipher the conversation . Unfortunately, there are no proofs for how hard it is for a third party to decipher the conversation, although in practice, we don’t know any way to accomplish that in a short time.
Quantum communication (imagine a quantum internet, which allows quantum bits to be transmitted) can be used for a much safer encryption: it can be proved that the conversation can’t be deciphered by a third party, not even in infinite time.
Implications for the end user
Quantum encryption rocks, but is not necessary: one can get along fine with classical encryption schemes, where it might be possible to break the encryption in a billion years. Although many of the computational assumptions, used in current classical encryption, will not hold when quantum computers will be available (see the following section for more details), there are several classical encryption schemes, conjectured to be secure even against quantum attacks. Currently, these schemes are not commonly used, mainly, because there is no real need for them.
Quantum encryption has the additional benefit that it has no unproved assumptions. Also, the encryption and decryption are much simpler in terms of computational resources. Thus, they can be preformed much faster compared to classical encryption.
Description: given an integer , find a non trivial divisor of .
There is no known efficient classical algorithm for this problem (i.e. with running time polynomial in the length of the input). Why is this problem important? Multiplying two prime numbers, and is computationally easy, but the inverse operation, factoring, is computationally hard. For example if I ask you to find the factors of 7597, it would take you a lot time, but on the other hand, verifying that 7597 is indeed 71*107 is easy.
Most modern encryption schemes use the computational assumption that it is unfeasible to factor large numbers.
Peter Shor discovered that quantum computers can factor large numbers efficiently. Therefore, almost all of the classical encryption schemes used today will be insecure, once quantum computers are available.
Implications for the end user
Grandpa is not a hacker – he is not interested in breaking encryption. Furthermore, these breakable encryption schemes will not be used once quantum computers are a reality, because they will be insecure. See the previous section for more details about that.
Hackers may be able to break messages that were sent using “old” encryption schemes.
Description: Given a list of items, and a certain property, find an element in the list with that property.
Let’s first look at an example: suppose a company has a list containing its customers. The company needs to know whether John Doe is indeed a customer. If the list contains elements, then, one needs to go over the list one by one, and therefore steps are needed to decide whether John is indeed a customer.
In terms of the description of the problem, the property in this example is: the element is “John Doe”.
Quantum Computers can answer this problem faster using Grover’s algorithm: instead of steps, only steps are required. (Roughly speaking, the number of digits in the number of the steps is halved in the quantum algorithm, so 1000 instead of 100000).
Implications for the end user
If the list was sorted, then to decide whether John Doe is in the list takes less time, just like in a phone book. Sorting a list with elements takes order of steps (instead of steps which are required to create an unsorted list with elements, so 6000000 instead of 1000000, since, the log of a number is approximately the number of digits of the number). This logarithmic factor is a small price to pay, because from that point, searching for an element takes instead of steps, which is why looking up a number in a phone book by the name takes little time, whereas looking up a person by his number takes a very long time.
To conclude, keeping the list sorted is a much better solution for the problem we have described, and unfortunately, quantum computer offers no added value either for sorting, or for searching in a sorted list.
Notice that the property which can be solved using Grover’s search can be arbitrary. Imagine that you want to search your database using custom queries, which are not known in advance. For example, find a person who has two “r” ‘s in his name. There is no way to “sort” the list according to this kind of queries when items are inserted. Therefore, the best way is a brute-force search which requires iterating over the list and checking for each person whether the name contains two “r” ‘s. Scenarios like these are not very common these days, but this might be because it takes too much time to answer such queries using classical computers. Maybe, when quantum computers are available, answering these queries will become feasible, and therefore will become more common. In any case, this looks like a property that is important for data centers; not for end users.
Description: money with a bunch of nice properties.
- It can’t be forged.
- The verification that the quantum money is legitimate does not require any communication.
- The money can be transferred by using quantum communication.
Some background: the bills and coins in use today are made in such a way that makes them hard to forge. But in what sense? There is a constant cat-and-mouse game between the mints and the counterfeiters, but there is no rule-of-nature or any other formal way to assess how hard it is. Money can be viewed as a cryptographic primitive. So, why not create money where the security is based on the hardness of computational problems? This is exactly what quantum money does. So, a quantum coin is made of qubits, which are similar to classical bits. So, you can imagine that your quantum money will be stored on your quantum mobile phone. When you receive the money, you need to apply a quantum algorithm, which verifies that the money you received is indeed legitimate.
The caveats: The current scheme is still a “work in progress” and currently its security isn’t proved: there are no clear assumptions under which the scheme is secure. Scott Aaronson recently gave a talk about his work with Paul Christiano at the Hebrew University about a different scheme that made some improvements with respect to the assumptions needed for the security proof, but it is still unpublished, so I’m not sure about the details.
Two other minor caveats are: the money can be forged with exponentially small probability (so, this has no significance), and the money can be used only a polynomial number of times before the money should be replaced by the bank (which is similar to the physical deterioration of paper bills).
Implications for the end user
There were several classical suggestions for money which were based on cryptographic assumptions, but all of them lack property 2: a transaction requires communication over the network.
Notice that quantum money requires quantum computation to verify the legitimacy of the money. Communication is a cheap and useful resource, so why not use it? These days, mobile phones have signal pretty much everywhere, so, there is little benefit for the quantum protocol, which does not need communication.
The alternative (classical) schemes have the following benefits:
- They do not require quantum computers.
- The security of these schemes is based on well known cryptographic primitives.
- Some schemes require a trusted party (such as the bank) to manage all the transactions. The bitcoin scheme, proposed in 2009, requires communication (so it doesn’t have property 2), but it does not require a trusted third party. Instead, it uses a protocol over a peer-to-peer network which prevents double-spending (spending the same coin twice, for two different transactions). The following article contains a good explanation, and this is the original proposal, which requires some background. I don’t know whether the current implementation is secure against quantum attacks, but I am not aware of any reason why it couldn’t be made secure.
There may be other benefits to quantum money in the future, such as better anonymity.
Description: sending quantum bits from one place to another, without using quantum communication. Teleportation requires classical communication and pairs of entangled qubits shared in advance.
One of the peculiarities of quantum mechanics is that quantum information cannot be copied. There is no problem to send quantum information by using quantum communication. When there is no quantum channel available, Alice can send quantum information to Bob, using classical communication and entangled qubits, in a protocol known as teleportation. I will not go into the meaning of entangled pairs are, but they can be viewed as a resource that requires quantum communication at a previous point in time. Since information in a quantum state cannot be copied, when the information appears on Bob’s side, the information on Alice’s side vanishes. In this aspect, it is similar to the teleportation process done in Star-Trek.
On the other hand, quantum teleportation is not a way of transporting a physical system, it moves only the information stored in a system. This is similar to sending files over the internet, where bits of the information are transmitted, and not the physical entities where the bits are stored.
Teleportation can be used if quantum communication is not available, but requires having entangled pairs in advance. Quantum communication is a resource available even today, whereas quantum teleportation is a replacement for: “send a qubit by using quantum communication”. So, there seems to be little benefit. Furthermore, the requirement of shared entanglement means that quantum communication must be used at a previous point in time.
Teleportation may turn out useful, especially as a building block.
Furthermore, one can imagine that your quantum mobile phone would have 3 levels of signal: (i) none (ii) classical and (iii) quantum.
Suppose, a user loses his strongest type of reception, and still wants to use quantum communication. He can prepare a stash of entangled pairs with the operator at a previous stage, and then, when he loses his quantum signal, he can use the classical signal together with the entangled pairs to send the quantum information to the operator, and vice versa.
Alternatively, one can imagine that the classical communication speed will be much faster than the quantum communication speed. The same idea can be used to get the higher speeds to transmit quantum information.
Simulation of physical systems
One of the ways to understand the properties of a complex system is by simulating it: in various settings there is no known analytic analysis, and simulating the system is the best we can do. Simulating a generic quantum system efficiently is not possible on a classical computer (as far as we know), but can be done on a quantum computer.
Implications for the end user
Simulation of quantum systems is a common procedure in scientific research including physics, chemistry, biology and other fields. In fact, simulating quantum systems is one of the main uses of supercomputers (I vaguely remember someone saying it takes up roughly 50%, although I don’t have the resource to back it up).
Solving Linear Equations
The problem: Given a system of linear equations, find a solution.
Here is an example for a system of two linear equations, involving two variables:
One can verify that is the only solution.
If the number of equations is , the time it takes to solve it using the “high school approach” is of order elementary operations; better algorithms are known.
There exists a quantum algorithm which achieves an exponential speedup, that is, it takes order of . To achieve the exponential speedup, some assumptions are needed regarding the numerical stability of the solution, and the form of the equations (more explicitly, the running time depends on and the constraints matrix must be sparse) . Unfortunately, the algorithm doesn’t provide the solution to the equations; it only provides a quantum state which is a solution. This means that only some properties of the solution can be extracted. For example, if the solution is , it is possible to approximate , for a large class of matrices .
Implications for the end user and the market
Solving linear equations is a standard tool in today’s software in fields such as image processing, robotics, machine learning and almost in all the fields of computer science.
There are several caveats: finding the solution takes polylogartihmic time, however, specifying the linear equations takes up much more. Therefore, the specification of the problem becomes a real bottleneck. It is also unclear whether the numerical requirements, and the limited properties that can be extracted from the solution kill many potential applications.
Nevertheless, there is a considerable chance that this will become useful.
One can see this post as a party pooper.
There are more positive interpretations:
- Just as super-computers are not targeted for grandpa, quantum computers are (not necessarily) targeted for grandpa. This does not mean that they are useless. Thank Reshef for this point.
- Many people in the quantum computation community are looking for quantum applications which can be used by the end user, and this is a worthy goal. My hope is that when such applications are found, they will get the credit they deserve.
- Future computers may be quantum computers only because their building blocks will be extremely small where quantum effects take place. I certainly believe this will happen. This means that the hardware will be based on quantum mechanics, yet the software might remain classical. Therefore, quantum error correction and fault tolerant quantum computation may be necessary.
Predicting the future is generally risky, and in particular in this case, since quantum computation is a relatively immature field:
- The field gained interest only in the mid 90’s.
- Simulation of more than several qubits (the analog of classical bits) on a classical computer is impossible; therefore, learning by trial and error is currently impossible.
New discoveries that would effect the end user may emerge in the future. Who knows, maybe we’re in the Trough of Disillusionment?