12

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


7

Classical Hamiltonians By the spectral theorem, for every Hamiltonian there exists a basis in which it is diagonal. Thus, it is not correct to say that diagonal Hamiltonians are classical since this would apply to all Hamiltonians. A Hamiltonian $H$ which is diagonal in a product basis $\mathcal{B}$ is sometimes described as classical, because the evolution ...


6

Usually, one defines classical states by first defining some "classical" orthonormal basis. Then a classical state is any state which is diagonal in this basis. Every classical state is then just some probability distribution written on the diagonal of some matrix. Note that all classical states expressed in this way commute. On the other hand, you ...


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


5

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


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

The problem is that the classical analogue has to have physical elements and operations for each amplitude, instead of for each qubit. Here is a quantum circuit for the 16-amplitude Fourier transform: Here is a butterfly diagram for the 16-state Fourier transform (from here): Each hadamard operation in the quantum circuit is an entire butterfly layer in ...


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


3

Nonclassicality in general I should start by pointing out that there is no univocal notion of "(non)classicality". To name a few examples, in the context of quantum optics one might call a state "nonclassical" if it cannot be written as a convex combination of coherent states. Or when entanglement is involved you might call "...


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

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

$$I(A:B)=S(A)+S(B)-S(AB)$$ $$J(A_{\{\Pi_{i}\}}:B)=S(A_{\{\Pi_{i}\}})+S(B)-S(A_{\{\Pi_{i}\}}B)$$ $$I(A:B)-J(A_{\{\Pi_{i}\}}:B)=S(A)-S(AB)-S(A_{\{\Pi_{i}\}})+S(A_{\{\Pi_{i}\}}B)$$ Since $$\rho = \sum_j p_j \pi_j\otimes \rho_j,$$ it is invariant to the measurements performed on the subsystem A, after the results are forgotten, so $$S(A)=S(A_{\{\Pi_{i}\}})$$ and ...


2

To pose a very simple answer to compete with all these complex (but also excellent) answers: the Ising model is a classical Hamiltonian because it is diagonal as it's written and therefore all of its eigenstates are classical states in the $S^z$ basis (no superposition required). Time evolution produces no mixing of the $S^z$ basis. All observables (that ...


2

While Adam's very detailed answer is probably emaculate, it's a bit long so for people that want a shorter answer, I'll give a much more compact alternative. This is not at all to challenge or try to refute Adam's answer at all. "What do they actually mean by a commuting hamiltonian?" In the specific case in your question, they are referring 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

$I_{acc}(\rho^{XA})=S(\rho_{A})-\sum_{x}p(x)S(\rho_{A}^x)$ $I(X:A)=S(\rho_{x})+S(\rho_{A})-S(\rho_{XA})=S(\rho_{x})+S(\rho_{A})-(S(\rho_{X})+\sum_{x}p(x)S(\rho_{A}^x))=S(\rho_{A})-\sum_{x}p(x)S(\rho_{A}^x)=I_{acc}(\rho^{XA})$ as the state is classical-quantum. The mutual information of product states is the sum of the mutual information of the individual ...


1

I'm assuming you are referring to this paper: Uncertainty, Monogamy, and Locking of Quantum Correlations. In proposition 6, it's not clear to me if they are referring to the same product state that you are considering. However, in that paper, where they mention the additivity of accessible information, along with the Holevo paper, they also cite the ...


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


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