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 ...


3

Answering your precise question: mixing the four scenarios is not particular to Hardy's argument, it is done in all nonlocality proofs. The fundamental assumption is that the distribution of the hidden variables doesn't depend on the measurement setting, i.e., whether BS2$^+$ or BS2$^-$ are there, so that we can actually use the different measurements to ...


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 ...


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.


1

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(...


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