Another thought about it is that many physics experiments can be regarded as “depth one quantum circuits” so that moving from depth one to depth two can already be powerful. (Again I am not talking about computational complexity but about creating interesting quantum states.

]]>I’m not sure exactly what assumptions are made in Dorit’s paper, but in ours the only necessary requirement for the larger system is that operations are linear. If there is a way to perform non-linear operations deterministically then the privacy theorem does not hold.

]]>All I meant by “philosophical” was that a quantumly generated coin flip might possibly not be random to “God”. But it cannot be predicted by observers that live within the universe.

]]>It also turns out that Levin has an arxiv paper linked from the article I linked to, where he considers a question sort of like mine. He hypothesizes that these physics experiments won’t reveal anything mathematically interesting, and presents that a bit more formally, as sort of an extended Church-Turing thesis.

]]>*Yes, we can test quantum mechanics while assuming its *correctness only on very small systems, plus some very *weak assumptions on larger systems. So you do not have *to believe in quantum mechanics to get convinced – but *you do have to assume SOMETHING – you do have to *assume something that generalizes both known quantum

*_and_ classical dynamics.

That’s really cool. Is that in your paper (perhaps it’s implicit and I missed it)? If it’s not too complicated, could you tell what would be the assumptions you need on larger systems?

I’d bet the commuting problem is in NP, or at most in QCMA: this paper arXiv:0803.1447 has some nice results concerning frustation free commuting Hamiltonains which seems to point in this direction, modulo the fact that I don’t understand the argument 🙂

]]>Okay, I will say a little more, and try to steer the discussion away from semantics.

My position is that yes, while technically you cannot test whether any dynamics exists outside of BPP without actually building a quantum computer, such a test is only impossible if you are partly skeptical of quantum mechanics itself. If you believe quantum mechanics, then you can do a test in which a very small physical system computed more than is classically possible using its own limited computational resources, even if it can be simulated by some other, much larger computer.

But again, if you do not entirely believe quantum mechanics, then who is to say how much computational power is available to ten trapped ions, say. Maybe they have twenty megabytes of storage and the equivalent of a megahertz processor. That would be plenty to simulate ten qubits, and it would also be easy to simulate with modern computers, so it would prove nothing that the ten ions can do a Grover search.

*do physics whizzes these days believe (and does QC require) that there is such a thing as true randomness in the physical universe?*

Quantum computation does not separately require “true randomness”. However, true randomness is a consequence (not an assumption) of quantum probability, which is my name for the axiomatic foundation of quantum mechanics. In other words, you can construct a coin flip using a measurement protocol with some qubits. That coin flip may or may not be “random” in some philosophical sense; but if you or any other physical actor can predict this quantumly produced coin flip, even with the aid of a large computer, then quantum mechanics is wrong.

]]>DQC Digital Quaker Collection

DQC Data Quality Control

DQC Double Quarter Column (print advertising)

DQC Double Quantum Coherence

DQC Design Quality Control

DQC Data Quality Center

DQC Delta Quadrant Command (game)

DQC Delaware Quality Conference

DQC Definite Quantity Contract

DQC Directional Quasi-Convexity

DQC Dame Quaker’s Club (gaming)

DQC Dream Quest Communications

DQC Dosimetric Quality Control

DQC Domain Quick Connect (Apollo)

DQC Disk Quota Control (Microsoft Windows NT)

DQC Deemed QC

DQC Division Quality Council

DQC Dose and Quality Control

DQC Departmental Qualification Course

DQC Doomed Quantum Computation