11

To my mind, this theorem is not very well stated in this form, if taken out of context. Where it says "phase gates", this may be misleading. It means specifically just $S=\sqrt{Z}$ and not what I think of as a phase gate, which can have an arbitrary phase (but they have very specifically introduced their terminology about 3 pages earlier). This is a key ...


6

Yes, you are correct. Non-Clifford gates cannot be transversely implemented, instead implementation generally requires distilling magic states or Toffoli states. In practice this requires significantly more spacetime volume than Clifford gates. For reference, see the introduction sections here and here. The natural expectation would be that no quantum ...


4

Another way to think about this: To simulate what goes on in a quantum computer we have to do a lot of matrix math using $(2^N \times 2^N)$ matrices$^1$, and the action of (most) of the clifford gates can be actually be accomplished by applying some non-linear, low complexity matrix operation instead of a matrix multiplication. For example, the Pauli-X gate,...


2

There are two different aspects to your question: Firstly, nobody should be claiming that you can solve this exponentially faster on a quantum computer. If I evaluate $f(x)$ just $n$ times using $x=1000..0, 01000...0, 00100..0, ... , 00...001$, then each time I find a particular bit value of $s$, and hence I find $s$ with $n$ function calls. This is only ...


Only top voted, non community-wiki answers of a minimum length are eligible