I got to know Steve from his sporadic arrivals to Dorit Aharonov’s seminars at the Hebrew University while I was a grad student there. Even though we met infrequently and didn’t have a chance to meet in the last couple of years, his work and character strongly influenced me.

Steve was arguably the father of quantum information and quantum cryptography.

He had two major contributions: Quantum money – which I’ll expand upon later, and super-dense coding, which he discovered with Charles Bennett in 1992. They asked the following question: how much classical information can Alice send Bob by transferring him a qubit? It turns out that if they have shared entanglement, then the answer is precisely 2 bits of information. Super-dense coding was the first work that viewed entanglement as a resource for communication tasks, and demonstrated that entanglement provides a tangible advantage. The advantage here is due to Holevo’s bound – which showed that without shared entanglement, a qubit could be used to send only 1 bit of information (though, I’m not sure if they were aware of it at the time). This protocol was the precursor of quantum teleportation, a closely related protocol discovered a year later.

Edit: Gilles Brassard commented that super-dense coding was first invented by Wiesner in 1970(!), 22 years before finally getting published. Charlie emailed his original note of his conversation with Steve. Charlie commented that he “added the pencilled notation “False” a little later (maybe a week or so) when he [Or: that is, Steve] realized that all four Bell states could be distinguished by a joint measurement.”

His invention of quantum money was a tour de force, for reasons which will become clear shortly. So, what is quantum money? In his words, simply “money that it is physically impossible to counterfeit.” As far as I know, he started pondering about it during university strikes in 1968 at Columbia University, when he had some free time.

One of the key ideas in modern cryptography is to turn lemons into lemonade: the lemons are intractable computational problems, and the lemonades are the secure protocols. This is done by a security reduction, showing that in order to break the protocol, one essentially has to solve the intractable problem; hence, breaking it should take a very long time. The basic idea he had in mind is to use a different lemon, namely, the no-cloning property of quantum mechanics, to reason about the security of his quantum money scheme. To understand the challenges that he faced, one needs to remember that modern cryptography was invented in the mid-’70s, so the lemons-to-lemonade approach wasn’t invented, and the no-cloning theorem was discovered only a decade later! And even the model we take for granted, including qubits, how they can be manipulated, etc. had to be figured out, pretty much from scratch. So, his work is essentially a masterpiece of persuasive writing, explaining high-level ideas, and contains very few technical calculations. It’s hard to express how vastly different his writing style is from contemporary works, especially in cryptography.

He submitted his paper in 1969 to IEEE transactions on information theory. At the time, no one thought of quantum theory as a theory of information, and the manuscript was rejected. As far as I remember, he told me that he didn’t try to resubmit it anywhere, and that the message he received from most of the people around him (including his PhD. supervisor) was that these ideas aren’t “serious science”. Luckily, he sent copies of the manuscript to some of his colleagues, including Charlie Bennett, whom he knew from his undergraduate studies. As is well documented (see, e.g., Gilles Brassard’s piece here), these ideas were polished and later led to the development of Quantum Key Distribution.

The same manuscript that introduced quantum money also invented 1-of-2 oblivious transfer, which he called multiplexing. The catch? His result was, essentially, incorrect. A perfect 1-of-2 oblivious transfer, as he suggested is impossible; but imperfect variants are possible. It took more than 4 decades until André Chailloux, Gus Gutoski and Jamie Sikora fully resolved it. (And this work is part of a large project, tightly related to quantum coin-flipping, arguably, one of the deepest topics in quantum information science.) So, even though the scientific method (or, at least, its institutions) spectacularly failed in this case, the establishment had some reasons. In that regard, I recommend reading Asher Peres’s approach where he says that he “…was the referee who approved the publication of Nick Herbert’s FLASH paper, knowing perfectly well that it was wrong”. In other words, there are exceptional cases where even incorrect papers should get published. Unfortunately, there is no agreed-upon mechanism for that.

On a personal note, I have two vivid memories of him.

During my post-doc at Berkeley (2014), I came for a visit in Israel, and gave a talk about an adaptive attack on his scheme, based on a collaboration with Aharon Brodutch, Daniel Nagaj, and Dominique Unruh. The talk was at the Hebrew University and was still an ongoing project, and I was a bit nervous: I definitely didn’t want to insult him in any way. I remember Steve was only mildly interested during the talk. Later, I asked him for comments, and he kindly replied that this wasn’t how he imagined the quantum money would be used; for the attack to work, we assumed the attacker could ask for valid money back from the verifier. Of course, our goal was to spell out exactly how the scheme could be used securely, and non-trivial ways in which it wasn’t. This is exactly the type of questions asked in modern cryptography, and I feel he didn’t find these questions particularly interesting at the time.

Around the same time, I saw him on campus, and invited him to another lecture, this time, comparing quantum money and Bitcoin. He was familiar with Bitcoin (at the time, Bitcoin wasn’t as popular as it is today), and was very interested but refused. I offered him a ride, and tried to persuade him, but to no avail: the talk was at the Google startup campus at Tel-Aviv, and he was very concerned that there will be a security camera recording him entering the building. Last week I learned from his daughter, Sarah, (who was and still is very active in the Israeli Bitcoin scene), that they later viewed a recording of it.

In late 2020, I invited him for another lecture devoted to recent progress on quantum money and related topics, but he politely refused, since he was too weak to attend.

I would like to offer my deepest condolences to his family, friends, and colleagues. To read more about him and his work, see Scott Aaronson’s blog post.

Another attempt produced the following  classical (probabilistic) query complexity lower bound, which is based on combination of Scott Aaronson and Paul Christiano’s quantum money scheme and Farhi et al.’s quantum state restoration protocol. Andrew Drucker and Ronald de Wolf wrote a beautiful survey about Quantum Proofs for Classical Theorems. I think this is another example for a theorem which is hard to prove without using “the quantum lens”. Unfortunately, I couldn’t find any use for this theorem.

There is an interesting open problem at the very end. Feel free to skip.

Here is the setting: There exists an unknown subspace , where Your goal is to find a basis for . We define   . Note that . You are given access to two (classical) oracles: and . The input for both oracles is a subset (not necessarily a subspace)  . Since we are interested in query complexity (and not an algorithm) it is not important how the input for the oracle T is specified. For an input T, the oracle outputs 1 with probability , and 0 otherwise; The oracle outputs 1 with probability , and 0 otherwise.

Claim: Finding a basis for  given these two oracles requires queries. Alternatively, finding an element requires queries.

Remark: I have never encountered query complexity analysis of a probabilistic oracles before. Probabilistic oracles may be of interest for other reasons.

Proof sketch:

We’ll show a lower bound for finding a basis for . The lower bound for finding a non-trivial element of follows easily from that.

Let and be the quantum oracles of and respectively (that is, applies a phase shift for every , and similarly for ). Aaronson and Christiano proved that queries to these quantum oracles are necessary in order to create the state given a single copy of the state . One can create many copies of if one knows a basis for .

But the oracle we mentioned is somewhat different. We can easily implement an oracle which outputs 1 with probability , and 0 otherwise, by querying the membership oracle S a random element of T. But,  the oracle has in the denominator (not ), which is arguably more informative for |T|’s bigger than |S| .

One can simulate a query to with queries for and , if one holds a single copy of , using the quantum state restoration procedure by Farhi et al.  They have shown that given a state and a 2-outcome projector onto that state, it is possible to simulate any 2-outcome measurement over the state,  using queries (in expectation) to the projector , without destroying the state . In our case, the projector which we want to simulate is  , the state is , and the 2-outcome projector can be implemented using a single query to and a single query to (this is  a nice exercise – see Aaronson & Christiano’s paper for details). To conclude, implementing a query to , that is, a query which outputs 1 with probability can be done using queries to and , if one holds a single copy of the state (and similarly for .  Finding a basis for breaks the security of Aaronson & Christiano’s money scheme, therefore, at least queries for and  are required.

Side comment:

One of the most intriguing aspects of the paper by Farhi et al. is that they provide an operational interpretation for the Schmidt rank. This fact is not explicit in their paper, so I thought it is worth mentioning.

The following process has an expectation time , where is the Schmidt rank of the state  to its partition to the first qudit (of dimension d) and the rest of the system:
1. Init: start with the state .
2. Repeat:
2.1 Replace the first qudit (of dimension d) with the maximally mixed state. Denote this mixed state .
2.2 Measure using the the two outcome measurement .
3. Stop if the outcome is  .

I’ve wondered whether the above process can be used as a definition for the Schmidt rank of a mixed state. I had a hard time comparing it to the definition by Barbara Terhal and Paweł Horodecki here. If you have any insights regarding that, I’ll be happy to listen!

There is another quantum / classical issue that I find interesting, which has a different flavor.

I’ll try to keep this post as simple as possible, and accessible both to the quantum, and the bitcoin / cryptocurrency community.

The main problem with digital money is the “double spending” problem: suppose Alice has 1 coin in a digital wallet. She could pass that “virtual coin” both to Bob and to Charlie. Who owns the coin – Bob or Charlie? Bitcoin solves this problem elegantly using a “proof of work” mechanism, which I won’t get into in this post. There are plenty of good resources that explain that.

Quantum Money solves this problem by exploiting a quantum phenomenon, which is called the No Cloning Theorem: copying an unknown quantum state is impossible.

The main advantage of quantum money with respect to bitcoin is anonymity. In the bitcoin protocol, all the transactions are public, and saved on a data-structure called the “block-chain”, and although a person may use multiple addresses, the anonymity isn’t guaranteed. On the other hand, a transaction using quantum money does not leave a trace. A second advantage is that if two persons meet, communication isn’t needed in order to make a transaction. This is not the case in bitcoin, which requires Alice to digitally sign a message saying “Alice transfers 1 bitcoin to Bob”, and propagate it to the network. A third advantage is that quantum money does not require a network of machines that uses a lot of honest computational power in order to run securely (otherwise, there is a problem of 51% attack). Quantum money can also be used as digital money: since quantum money is based solely on quantum information, it can be transferred on the “quantum internet” easily, just like bitcoin. Both of them are “peer to peer” in the sense that the transaction does not require a trusted 3rd party, like a bank or a broker.

It may seem that quantum money is  better in every aspect. There is a catch, which I believe was unnoticed, which is accountability.

Suppose Alice wants to buy Bob’s bicycle, using bitcoin over the internet. Bob emails his bitcoin address to Alice (and digitally signs the message). Alice sends bitcoins to Bob’s address. Now, Bob runs away with the money. When using bitcoin, Alice can prove to the police that she paid Bob: she has a copy of Bob’s address (signed by him), and the record that she paid to Bob’s  address appears on the block-chain. Therefore, the police can point the finger to Bob.

Let’s look what happens in the quantum case: when Alice sends Bob the quantum money, it leaves no trace. Bob can argue that he didn’t get the quantum money, and Alice can’t prove to the police that she sent Bob the quantum money.

One way to solve it is to use “quantum escrow”, which is not needed in bitcoin: Alice can prove that she paid Bob, without the assistance of a trusted party that was involved in the transaction.

I wish to stress that this “non-accountability” property also occurs in other quantum cryptography protocols, for example in quantum coin flipping, quantum bit commitment, and others. I’m not sure whether this could be overcomed. The main missing ingredient is the analogue of digital signatures of quantum information.

“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.

Encryption

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.

The Market

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.

Factoring

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.

The market

Hackers may be able to break messages that were sent using “old” encryption schemes.

Database Search

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.

The market

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.

Quantum Money

Description: money with a bunch of nice properties.

1. It can’t be forged.
2. The verification that the quantum money is legitimate does not require any communication.
3. 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.

The Market

There may be other benefits to quantum money in the future, such as better anonymity.

Quantum Teleportation

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.

The Market

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

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.

Conclusions

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?