One of the explanations I have encountered for why quantum computation can provide speed-up over the classical is a picture that in the Hilbert space much more paths are allowed quantum-mechanically than classically. Indeed, it seems that we are only allowed to travel along computational axes classically, but quantum-mechanically we can take shortcuts. Is this picture morally correct? Is it possible to present some very explicit illustration? Say for the Deutsch problem or for the Grover algorithm with minimum qubits?

  • 1
    $\begingroup$ How the classes of quantum circuits that are known to be simulable efficiently on a classical computer (e.g., stabilizer circuits) fit into this picture? $\endgroup$ May 25 at 11:10
  • $\begingroup$ @Egretta.Thula (pure speculation) the path that the initial state traces in the Hilbert space in these algorithms can be well (with small overhead) approximated by classically allowed paths. $\endgroup$ May 25 at 11:15

A few thoughts:

If you identify a few of the axes of an $n$-qubit state space, those corresponding to bit-strings $|s_1,...,s_n\rangle, s_i\in\{0,1\}$, with "classical states", then it might seem natural to say that "quantum algorithms are allowed to take shortcuts". But I think this picture is actually faulty. When you say this, you are probably thinking about the quantum state moving in state space in directions that a classical state is not allowed to go. But what would a corresponding "classical evolution" look like?

There is no nice way to picture the evolution of a classical state in the same way you picture a quantum state in Bloch-like representations. A classical state doesn't evolve smoothly between the "classical axes". Rather, it jumps between them. But then what is such a picture telling you? It doesn't seem particularly useful to talk about "shortcuts" when the corresponding classical evolution would be pictured as a sequence of discrete jumps.

  • $\begingroup$ Hi, thanks for thoughtful suggestions! I'm afraid this is not yet satisfactory for me. (1) indeed, I imagined a classical circuit as a series of jumps along computational axes in the Hilbert space. Similarly, a quantum circuit gives a series of jumps not restricted by computational axes (but restricted by the set of gates one can implement). (2) I do not see what is wrong with treating $|0,0\rangle>$ as a "classical state". Any classical circuit can be run on a quantum computer along the lines of (1). $\endgroup$ May 25 at 10:18
  • $\begingroup$ And yes, cloning of generic quantum states is prohibited, but cloning of orthogonal is fine, right? And "classical" states (=computational basis states) are orthogonal. $\endgroup$ May 25 at 10:18
  • $\begingroup$ @WeatherReport you make a fair point about cloning, I removed that part. Regarding the "shortcuts picture", my point is that if the evolution is inherently discrete, what does it mean to talk about "shortcuts"? When I think about shortcuts I think of being able to reach the destination following some alternative path. Now, quantum gates can always be pictured via the underlying dynamics as following some continuous path in state space, so you might say that they follow some "hidden trajectory", but you cannot picture the "classical evolution" in the same way, so it seems unfair to compare them $\endgroup$
    – glS
    May 25 at 10:54
  • $\begingroup$ Well, I'd say that in a quantum circuit model the evolution is not continuous. After each application of a gate the state of the system jumps. Comparing complexities is comparing the number of steps. I have the following picture in my mind (perhaps totally inaccurate): try going from one vertex of a cube to its diagonal opposite. Classically you can only go along edges, quantum mechanically you can presumably go along the diagonal itself. $\endgroup$ May 25 at 11:12
  • $\begingroup$ @WeatherReport but if you only think in terms of discrete jumps, what's the advantage of trying to picture it in the state space? You might as well just represent the computation as you'd normally do: as the sequence of intermediate states that the algorithm "explores" during the computation. Though you might represent the computation as a sequence of possible states with the connections allowed by quantum gates. You'd then get a graph whose edges denote states connectible via gates allowed during the computation. But even with this, how would you represent superpositions? $\endgroup$
    – glS
    May 25 at 11:15

OK, my question has some suspicious implicit assumptions. Usually the point of the algorithm is not to prepare a given state $|B\rangle$ from an initial state $|A\rangle$. If $|B\rangle$ encodes the solution to a problem, and if we know $|B\rangle$ right from the start there no need to build an algorithm. Rather, the problem usually is to construct a state $|B\rangle$ satisfying certain properties (say $U_{\text{oracle}}|B\rangle=- |B\rangle$ ).

So in general the question "find the shortes path between states $|A\rangle$ and $|B\rangle$" does not make much sense. I can think of one exception though -- Grovers algorithm. It should be possible to build a classical circuit that calls an oracle $N$ times and returns the marked state with certainty. One can ask if one can build the same circuit (approximately) out of the quantum gates instead of classical. My imagination pictures something like cutting along the diagonal path in the $N$-dimensional Hilbert space (while classical paths can only travel along computational axes and turn right angles) and from Pythagoras theorem that should give about $\sqrt{N}$ advantage. Of course this is no proof, but this does not seem too implausible to me.

OK, the problem with this argument then seems to be that any quantum algorithm should be possible to approximate with a classical algorithm with no more than a quadratic slowdown. So, do we all agree that $BQP=BPP$ is not settled in the affirmative?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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