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 , 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!