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 ...
3
This question was solved in 2014 by Vértesi and Brunner: they found a quantum state with positive partial transposition that violated a Bell inequality. The conjecture that all states with positive partial transposition do not violate any Bell inequality was known as the Peres conjecture, so they disproved it.
As for your parenthetical question, whether all ...
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(...
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 ...
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
