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 ...
5
If you treat the gate sequence as fixed then by the same logic you can treat the actual gates as fixed. No parameters is better than polynomial number of them :)
But the problem is not with this. Let's say we want to implement Shor's period finding routine. The output of the unitary gate sequence will be some state in $2^n$-dimensional Hilbert space. We do ...
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,...
3
Is this just bad phrasing (or a typo) on Wikipedia's side, or am I missing something?
It does sound like bad phrasing. The idea here is that our set of observables is not necessarily mutually (pairwise) commuting. If you have three observables $A$, $B$ and $C$, and $[A,B]=0$ and $[B,C]=0$, then you're right that the measurement of $A$ will have no effect on ...
2
You're presumably thinking of a spectrum with classical mechanics at one end and quantum mechanics at another, with some hazy "classical-quantum" in between. That's not a great way to think about it. Classical mechanics is more of a practical approximation of quantum mechanics under certain conditions (cf. classical limit), as per the correspondence ...
2
You seem to be mixing two very different concepts here. Quantum cloning is talking about the absolute limits of what is theoretically possible in a perfect world. In this absolute theoretical limit, yes we can derive how well quantum cloning can work, and we also know that classical cloning is nominally perfect.
There is then a separate question of how well ...
2
I believe the issue you are missing is entanglement, which is an essential resource in quantum computing algorithms. Since we generate entanglement between these qubits, we can no longer think of independent subspaces of the Hilbert space where the final state can be represented as a tensor product of these subspaces. This is because an entangled state can't ...
2
The issue is that you are confusing the notions of Komogorov complexity and computational complexity. Kolmogorov complexity (roughly) means the smallest amount of data that you need to provide in order to completely specify an object. Computational complexity (roughly) refers to the minimum number of time steps that it takes any Turing machine to convert an ...
2
As Danylo Y have answered, the key is you don't need to read out the entire quantum state at the end of the quantum algorithm to get your answer. There is another algorithm, called HHL algorithm, which is design to solve linear system of equations $Ax = b$. It provides an exponential speed up, and uses $O(\log(N))$. If you think about it, it already takes $O(...
1
Not quite. Consider the following no-signalling distribution $PR_1$ which I will write in the form
$$
\begin{pmatrix}
p(00|00) & p(01|00) & p(00|01) & p(01|01) \\
p(10|00) & p(11|00) & p(10|01) & p(11|01) \\
p(00|10) & p(01|10) & p(00|11) & p(01|11) \\
p(10|10) & p(11|10) & p(10|11) & p(11|11) \\
\end{pmatrix}...
1
Yes. As you've effectively said, all cases satisfying (2) are in a polytope and therefore convex. All the vertices of that polytope are deterministic strategies, and so every point inside the polytope can be described as a convex combination of these, and that gives you (at least) one such local realistic explanation.
Only top voted, non community-wiki answers of a minimum length are eligible
