23 votes
Accepted

How can classical bits be copied if qubits cannot be copied?

TL;DR: The ban on copying is not nearly as universal as it might seem. No-cloning theorem actually allows copying as long as it is limited to orthogonal states. Classical information is the type of ...
Adam Zalcman's user avatar
  • 22.3k
17 votes
Accepted

Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

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 ...
DaftWullie's user avatar
9 votes

Why are diagonal Hamiltonians considered classical?

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 ...
Adam Zalcman's user avatar
  • 22.3k
6 votes

Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

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 ...
forky40's user avatar
  • 6,728
6 votes

Why are commuting density operators said to be "classical states"?

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 ...
Rammus's user avatar
  • 5,743
5 votes
Accepted

What are some examples of uncomputability with quantum computers?

There was some initial characterization of quantum computers as going beyond Turing. But this is not the way we see things today. Around 1982, Richard Feynman stated of his proposed quantum computer/...
Mark Spinelli's user avatar
5 votes

Why are diagonal Hamiltonians considered classical?

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 ...
user1271772 No more free time's user avatar
5 votes

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

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. ...
Danylo Y's user avatar
  • 7,184
5 votes
Accepted

Are inseparable states with positive partial transpose nonlocal?

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 ...
Mateus Araújo's user avatar
4 votes
Accepted

How does quantum contextuality relate to mutually commuting observables?

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 (...
Sanchayan Dutta's user avatar
4 votes
Accepted

Understanding Hardy's proof of "nonlocality without inequalities"

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 ...
Mateus Araújo's user avatar
3 votes
Accepted

Quantum fourier transform with classical vibrations

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: ...
Craig Gidney's user avatar
  • 36.8k
3 votes
Accepted

Why are commuting density operators said to be "classical states"?

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 ...
glS's user avatar
  • 24.8k
3 votes

Why are diagonal Hamiltonians considered classical?

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 ...
taciteloquence's user avatar
2 votes

Classical and quantum limits to classical copying?

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, ...
DaftWullie's user avatar
2 votes

If classical physics emerges in some limit of quantum mechanics, shouldn't there be intermediate classical-quantum computers?

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. ...
Sanchayan Dutta's user avatar
2 votes
Accepted

Does the CHSH inequality fully characterise the local polytope?

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) ...
Rammus's user avatar
  • 5,743
2 votes

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

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 ...
Differance_123's user avatar
2 votes

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

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 ...
tparker's user avatar
  • 2,731
2 votes

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

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, ...
KAJ226's user avatar
  • 13.8k
2 votes
Accepted

Why is the quantum discord of $\rho$ zero iff $\rho=\sum_j p_j \pi_j\otimes \rho_j$ for mutually orthogonal projections $\pi_j$?

$$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 ...
GaussStrife's user avatar
  • 1,115
2 votes

Circuit from finite group of gates and classical simulations

Let me give an answer which is not really intended as an answer (in that it doesn't address what I suspect the question is aimed at. For example, it does not cover the case of Clifford gates), and ...
DaftWullie's user avatar
1 vote

How is the additivity of accessible information, $\frac{1}{n} I_{\rm acc}(\rho^{\otimes n})=I_{\rm acc}(\rho)$, proved?

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 ...
QuestionEverything's user avatar
1 vote

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

Consider an $n$ qubit system. For each qubit you need to store 2 complex numbers, making $2n$ numbers in total. But if these qubits are entangled, then you can no longer store those numbers separetely....
usercs's user avatar
  • 471
1 vote

Does the CHSH inequality fully characterise the local polytope?

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 ...
DaftWullie's user avatar

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