A classical query complexity lower bound from quantum money

•November 19, 2014 • Leave a Comment

Recently, I’ve spent some time thinking about quantum money. In order to get some intuition about their security, I’ve tried to understand their weaknesses. One attempt was fruitful (warning: shameless self publication).

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 S\leq Z_2^n, where \dim(S) = \frac{n}{2}. Your goal is to find a basis for S. We define S^\perp = \{ y \in \mathbb{Z}_2^n | \forall x \in S,  \sum_{i=1}^n x_i y_i=0 \mod 2\} . Note that \dim(S^\perp) = \dim(S) = \frac{n}{2}. You are given access to two (classical) oracles: O_S and O_{S^\perp}. The input for both oracles is a subset (not necessarily a subspace)  T \subset \{0,1\}^n. 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 O_S oracle outputs 1 with probability \frac{ |S \cap T| }{|S|}, and 0 otherwise; The O_{S^\perp} oracle outputs 1 with probability \frac{ |S^\perp \cap T| }{|S^\perp|}, and 0 otherwise.

Claim: Finding a basis for S given these two oracles requires \Omega(2^{n/4}) queries. Alternatively, finding an element x \in S \setminus \{0\} requires \Omega(2^{n/4}/n) 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 S. The lower bound for finding a non-trivial element of S follows easily from that.

Let U_S and U_{S^\perp} be the quantum oracles of S and S^\perp respectively (that is, U_S applies a phase shift for every x \in S, and similarly for U_{S^\perp}). Aaronson and Christiano proved that \Omega(2^{n/4}) queries to these quantum oracles are necessary in order to create the state |S\rangle \otimes |S\rangle given a single copy of the state |S\rangle = \frac{1}{\sqrt{|S|}} \sum_{x \in S}|x\rangle. One can create many copies of |S\rangle if one knows a basis for S.

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

One can simulate a query to O_S with O(1) queries for U_S and U_{S^\perp}, if one holds a single copy of |S\rangle, using the quantum state restoration procedure by Farhi et al.  They have shown that given a state |\psi\rangle and a 2-outcome projector onto that state, it is possible to simulate any 2-outcome measurement over the state,  using O(1) queries (in expectation) to the projector |\psi\rangle\langle\psi|, without destroying the state |\psi\rangle. In our case, the projector which we want to simulate is  \Pi_T = \sum_{x \in T} |x \rangle\langle x|, the state is |S\rangle, and the 2-outcome projector |S\rangle\langle S| can be implemented using a single query to U_S and a single query to U_{S^\perp} (this is  a nice exercise – see Aaronson & Christiano’s paper for details). To conclude, implementing a query to O_S, that is, a query which outputs 1 with probability \langle S | \Pi_T |S\rangle = \frac{|S \cap T|}{|T|} can be done using O(1) queries to U_S and U_{S^\perp}, if one holds a single copy of the state S (and similarly for O_{S^\perp}.  Finding a basis for S breaks the security of Aaronson & Christiano’s money scheme, therefore, at least \Omega(2^{n/4}) queries for O_S and O_{S^\perp}  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 \chi d, where \chi is the Schmidt rank of the state |\psi\rangle to its partition to the first qudit (of dimension d) and the rest of the system:
1. Init: start with the state |\psi \rangle.
2. Repeat:
2.1 Replace the first qudit (of dimension d) with the maximally mixed state. Denote this mixed state \rho.
2.2 Measure \rho using the the two outcome measurement \{ |\psi\rangle \langle \psi|, I - |\psi\rangle \langle \psi | \}.
3. Stop if the outcome is  |\psi\rangle.

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!


Bitcoin vs. Quantum money

•September 5, 2014 • Leave a Comment

The following is my talk given at the Israeli Bitcoin Meetup.


Bitcoin vs. Quantum Money: the problem of accountability

•August 1, 2013 • Leave a Comment

Yesterday, I read a very nice article about the insecurity of bitcoin to quantum computers. This is not as trivial as it sounds!

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 a thousand Quantum computers

•July 2, 2012 • Leave a Comment

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

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.


Description: given an integer n, find a non trivial divisor of n.

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, p and q  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 n elements, then, one needs to go over the list one by one, and therefore n 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 n steps, only \sqrt{n} 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 n elements takes order of n\cdot\log n steps (instead of n steps which are required to create an unsorted list with n 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 \log n instead of n 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

 Grandpa isn’t likely to ponder over Schrodinger’s equation, or to simulate a quantum system.

 The Market

 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:

x_1 - x_2 = -4

x_1 + 2 x_2 = 17

One can verify that x_1 = 3,\ x_2 = 7 is the only solution.

If the number of equations is n, the time it takes to solve it using the “high school approach” is of order n^3 elementary operations; better algorithms are known.

There exists a quantum algorithm which achieves an exponential speedup, that is, it takes order of poly(\log(n)). 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 \kappa 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 \vec{x}, it is possible to approximate \vec{x}^t A \vec{x}, for a large class of matrices A.

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?

Protected: Optimal Construcive result for the Local Lemma

•March 16, 2010 • Enter your password to view comments.

This content is password protected. To view it please enter your password below: