Let's say we have a quantum computer with two registers taking in $m$ and $n$ qubits respectively, with $m$, $n$ suitably large. Let $f:\{0,1\}^m \rightarrow \{0,1\}^n$ be a one-way function. Set up the state $2^{-m/2}\sum_x |x\rangle|f(x)\rangle$, and then measure the second register only. We find it has the measured value $y$. So, we can infer the first register has the value $f^{-1}(y)$.

According to the Copenhagen interpretation, the registers never had any definite values until measurement. Thereafter, the value of the first register collapses to a value gotten from inverting a one-way function, which by definition is an NP problem not in P.

A hidden variables framework would say the first register had a definite value even before the transformation of $2^{-m/2}\sum_x|x\rangle|0\rangle$ into $2^{-m/2}\sum_x|x\rangle|f(x)\rangle$, so no problem there. MWI would claim the branching into many worlds also happened before this transformation. However, the Copenhagen interpretation appears to require the first register to invert a one-way function on the fly. What gives? Please clarify.

Just to make sure the Copenhagen interpretation insists the first register had no definite value prior to measurement, let's modify this experiment a bit. After the state $2^{-m/2}\sum_x |x\rangle|f(x)\rangle$ has been prepared, use the free will of the experimenter to decide A or B. If A, instead of measuring the register, the experimenter uncomputes the state back to $2^{-m/2}\sum_x|x\rangle|0\rangle$ and then back to $|0\rangle|0\rangle$ via a Hadamard transformation acting upon the first register, and then measures the first register. The measured value will always turn out to be 0, in conflict with the assumption that the first register had a definite value earlier. If B, the second register would be measured as before. OK, there's no guarantee option B would be chosen at any given try, but given enough trials, it's likely option B would be chosen at least once.

Sure, maybe the experimenter never had any free will in the first place (superdeterminism), or maybe the foreknowledge of the option choice was known by the quantum computer all along (backward causality). But that's not Copenhagenism.

  • 1
    $\begingroup$ Any possible function can be computed with a classical lookup-table in one step. I don't see a particular advantage for a quantum computer in that regard. The Copenhagen interpretation doesn't assign any values to a quantum system. It assigns values to the display of a classical measurement device that couples to the quantum system. $\endgroup$ – CuriousOne Sep 7 '15 at 6:18
  • $\begingroup$ @CuriousOne Please help me here. Some Copenhagenists claim measurement devices have to be classical. Others assert there are no classical devices whatsoever. Which one is the real Copenhagenist? $\endgroup$ – Pita Sep 7 '15 at 6:23
  • $\begingroup$ I have never met a Copenhagenist. I have met physicists who use the Copenhagen interpretation with a lot of success, though. I have, on the other hand, never met a serious physicist who has used the Multiworlds interpretation with any success. $\endgroup$ – CuriousOne Sep 7 '15 at 6:26
  • 1
    $\begingroup$ @CuriousOne 1) While you can "evaluate" a function with a single lookup, Grover's quantum algorithm allows you to invert a function in $\sqrt{N}$ time, which is considerably faster than the $N$ time it would take on a classical machine. 2) Your comment about not knowing any physicists who use many worlds with success is not surprising, since it makes no sense. $\endgroup$ – DanielSank Sep 8 '15 at 6:55
  • 2
    $\begingroup$ @Pita The phase "Copenhagen interpretation" is essentially useless since it means different things to different people and almost never means anything well-defined to anyone. I suggest ditching the phrase entirely and spelling out precisely what physics statements you'd like us to consider. $\endgroup$ – DanielSank Sep 8 '15 at 6:56


More explicitly, there's nothing particularly quantum about your scheme. This is easy to see because it fails the crucial test of replacing superpositions with mixed states. That means that you can replicate exactly the same protocol using the density matrix $$ \rho=\frac{1}{2^m}\sum_x|x⟩⟨x|\otimes|f(x)⟩⟨f(x)|. $$ If you measure the output register in the state $|f(x)⟩⟨f(x)|$, then the input register must be in $|x⟩⟨x|$, because the probability of detecting other states is zero in that case.

This means that your protocol can be performed perfectly well by a classical computer. Inside a big black box put a random number generator on $m$ bits and a calculator to compute $f$. Make the RNG write down a random $x$ on a slip of paper, pass that to the calculator, and write down the corresponding $f(x)$ on a second slip of paper. Put the slips of paper on sealed boxes marked $A$ and $B$, and output that.

Suppose further that you carry the boxes to spatially-separated locations and then you open box $B$ to reveal $f(x)$. Does that "force" Nature to instantaneously compute the inverse of $f$? To whatever extent it does, that's what happens in the quantum case.

(Note, however, that I'm not claiming that a hidden-variable mechanism "is actually happening" in the quantum case. There are other experiments you could perform which would rule it out. However, this particular case can indeed be modelled using hidden variables.)

  • $\begingroup$ Reread the last part where the experimenter makes a delayed choice between A or B. If A, the state is uncomputed with a Hadamard transformation on the first register leaving a measured value of 0. Only a superposition can do this. A mixed state can't. $\endgroup$ – Pita Sep 8 '15 at 15:26
  • $\begingroup$ That part is either inconsistent or unclear. If the output register has been measured then it will be impossible to 'uncompute' as stipulated. If the output register has not been measured, what makes you think you can apply the inverse unitary $U_f^\dagger$ more easily than we can turn the mixed state $\sum_x|x⟩⟨x|\otimes |f(x)⟩⟨f(x)|$ back to $\sum_x|x⟩⟨x|\otimes |0⟩⟨0|$? $\endgroup$ – Emilio Pisanty Sep 8 '15 at 16:05
  • $\begingroup$ If option A were chosen, no measurements would be made prior to uncomputation. Uncomputation doesn't require the evaluation of inverse one way functions. All it requires is a map of $|x\rangle|f(x)\rangle$ to $|x\rangle|f(x)\oplus f(x)\rangle$. $\endgroup$ – Pita Sep 8 '15 at 16:19
  • $\begingroup$ Whereas, on the other hand, classical uncomputation is done by simply deleting the output register. Again: how is your quantum protocol any more powerful than a mixed state? $\endgroup$ – Emilio Pisanty Sep 8 '15 at 16:21
  • $\begingroup$ The point of the delayed choice modification isn't to increase the computational power over a classical computer. It's to close the philosophical loophole of the first register having a definite value all along. $\endgroup$ – Pita Sep 8 '15 at 16:27

Your example is bad.

The reason your example is wrong, as covered by Emilio Pisanty, is that measurement of your state simply results in getting some random $(n, f(n))$ pair, which is very easy to do classically; in the theory-framework of a non-deterministic Turing machine we would say that it certainly contains a "probabilistic state" which has to "collapse" to a specific result:

import random
import hashlib
rand = random.SystemRandom()

def counterexample():
    f = hashlib.sha512()
    x = bytes([rand.getrandbits(8) for i in range(128)])
    return (x, f(x))

Your intuition is good.

Let $v :: \{0,1\}^n \to \{0,1\}$ return $1$ if the output is some target hash, $0$ otherwise. Then $g = v \circ f :: \{0,1\}^m \to \{0,1\}$ takes some input, feeds it into the one-way function, then tests if it is correct.

This function is precisely the sort of "database function" that Grover's algorithm works upon, and given $2^m \ll 2^n$ (so there is only one solution) we can recover the needed input in only $2^{m/2}$ operations rather than the classical $2^m$ operations.

Your intuition is not good enough.

The Grover's result is is faster than any classical computer can do it. However, we can also prove that Grover's algorithm is optimal: no quantum computer can do this faster.

The "complexity class" (like P, NP, PSPACE) for such quantum algorithms is called BQP, "bounded-error quantum polynomial-time." Since this only reduces the state space from $N \to \sqrt{N},$ the result is not enough to say that $NP \subseteq BQP.$ Obviously $N \to O(1)$ would yield this result and with a little effort you can see $N \to O\left([\log N]^k\right)$ doing it, since that maps $2^n$ to $O(n^k)$ which is polynomial; but the speedup $N \to O(\sqrt{N})$ is clearly not enough.

Notice that this doesn't prove a hierarchy one way or another between NP and BQP. The easiest way to see this is: you want to now say that NP is "bigger" than BQP, but we don't actually know that $P \ne NP$ yet, and $P$ is clearly in $BQP$, so if $P = NP$ then by virtue of $P \subseteq BQP$ we know $NP \subseteq BQP$ and BQP is bigger. They would probably then end up being the same complexity class.

If you're really interested in this relationship you should definitely read Quantum Computing Since Democritus: Lecture 10. One jargon word you probably don't know yet is "oracle": the complexity class $A^B$, where $A$ and $B$ are complexity classes in their own right, is the class of problems that can be solved by the computers which solve problems in $A$, if they were able to instantaneously solve problems in $B$ by asking some magic box, called an "oracle" for $B$, the answer to their problems. A lot of the inconclusive-evidence for two complexity classes being different is finding a C such that $A^C \ne B^C.$

It is known that $BQP \subseteq PP$, the class of problems that can be solved with probability $> 1/2$ by a classical computer which has access to a supply of good random numbers. (The complexity classes $BPP$ and $BQP$ improve the probability to $> 2/3$, which is significant because any limit strictly greater than 1/2 turns out to be equivalent: if the limit is only 1/2 then there is not necessarily a way to convert an algorithm to a 99.99% algorithm; if the limit is any amount greater than 1/2 there is.)

In fact, it is known that if you add postselection to $BQP$ there is a strict equality. Postselection is a very common practical thing we do in quantum experiments, we hook up a "coincidence counter" which only counts $x$ if $f(x, y)$ obtains. If you make this super-rigorous and explicit, e.g. in the many-worlds interpretation "I will generate a random vector $r$ and destroy the world if $v(f(r)) = 0,$ so that the only worlds I continue to exist in are ones where $r$ happens to hash to the right value", then you get back $PP$ again.

  • $\begingroup$ The delayed choice modification requires a hidden variable model more complicated than a mere $(x,f(x))$ pair. However, my question isn't about hidden variable models, but the Copenhagen interpretation. I am also not claiming that quantum computers can solve all NP problems. What I'm asking is whether the collapse of the wavefunction necessitates an NP computation behind the scenes within the context of the Copenhagen interpretation. $\endgroup$ – Pita Sep 8 '15 at 16:10
  • $\begingroup$ @Pita: Oh, then I mistook your question to be far more interesting. There is no possibility for "uncomputing" $\sum_x|x,f(x)\rangle$ without using the entanglement of the two states, which means it's not really a "delayed choice" (you cannot measure the first state and then perform the operations to force the first state to be $|0\rangle$.) So the answer is trivially that when you measure the second part, the first part collapses there-and-then; you get a consistent answer but it's no more complicated than the computer which chooses a number at random and computes $f(n)$ on it. $\endgroup$ – CR Drost Sep 8 '15 at 16:51

The Copenhagen interpretation (CI) doesn't say anything about the register. Or, rather, different versions of the CI may say different things about the register. The CI has a number of ingredients:

(1) The CI rejects the idea that quantum mechanics (QM) is an accurate description of how the world works.

(2) The CI claims that QM can nevertheless be used to make predictions somehow.

(3) The CI claims you have to describe the world in terms of classical concepts.

(4) How you use the classical concepts and QM is determined by an ad hoc algorithm.

(5) There is some philosophical stuff that claims to explain the previous ingredients. CI advocates do not all agree on what (5) consists of. This partly because there is no way to explain an ad hoc algorithm. As a result, all the options are lousy, so it's difficult to pick among them. One result of this problem is that there is no single answer to your question.

If you want a description of the CI that tries to take it seriously, see this article:



Not the answer you're looking for? Browse other questions tagged or ask your own question.