How does one extend local checkability to quantum complexity classes?

Question

How does one extend local checkability to quantum complexity classes like BQP? Or are quantum algortihms inherently holistic?

Answer 1

A preliminary guess at what it is you're looking for

I will give a preliminary answer, in the hopes that it might prompt you to elaborate on what promises to be quite a good question. I will assume you're referring to an idea along the lines of page 4 of [Arora+Impagliazzo+Vazirani 1993], which introduces the concept of "local checkability" as follows:

[...] we identify a general principle, the principle of local checkability, which appears to us to be at the root of the above-mentioned non-relativizing results [e.g. IP = PSPACE and MIP = NEXPTIME]. While this principle can be formulated in several ways, all of them express the fact that computation is a very local process, and hence checking the correctness of a computation is simpler than performing the computation itself.¹ We show that "local checkability" is a fact which does not relativize.

[...]

¹ This fact is also at the root of the Cook-Levin Theorem, and a preliminary version of this paper identified "local checkability" with the term "Cook-Levin Theorem".

Without going further into depth (awaiting a more precise description of the property which interests you), quantum computation does admit a notion of local checkability.

In the standard discrete-time models of quantum computation, all transformations are performed on small sets of bits: in this sense, computations are certainly local. So quantum computation is not any more holistic in principle than classical computation in this specific sense.

Local checkability vs. local performability

One might fear that the ability to perform local checks is undermined by the phenomenon of superposition, and in particular entanglement. If we have an operation O, which acts on a system A, how can we verify that the state of A after the operation corresponds correctly to the effect of O on the state of A before the operation, if the state of A cannot be isolated in the first place?

If we bear in mind that randomized computation is also subject to this complication — of systems not being independent of their environments — we can realise that perhaps entanglement does not cause any necessary "holisticness" to quantum computation. As usual, entanglement has in common with probabilistic correlations the fact that they are not product distributions; so merely failing to be a product distribution cannot be something which prevents local checkability of a quantum state, if it does not also prevent probability distributions from being locally checkable. Absent this particular spectre, we may hope that there could be pertinent techniques in the quantum regime. Of course, entanglement is more than just correlation of randomized events, because checkable properties of random correlations can be tested (with imperfect soundness) simply by sampling from the distribution, whereas this is not true in general of quantum states. Other techniques must be necessary.

The hint is provided by Arora, Impagliazzo, and Vazirani themselves in their invoking the Cook-Levin Theorem. I would suggest that we make reference to the techniques used to prove the QMA-completeness of LOCAL-HAMILTONIAN, which is the quantum analogue of the Cook-Levin Theorem. One might conjecture that any model of computation which is limited to locally performed operations, and has an analogue of the Cook-Levin theorem (i.e. complete problems for the class of constraint satisfaction problems admitting efficiently checkable certificates), is similarly subject to local checkability in some sense. A formal exploration of this idea might be an interesting subject in its own right, in the theory of computation.

Quantum local checkability via LOCAL-HAMILTONIAN

Not at all unlike the reduction of CIRCUIT-SAT to SAT, the classic proof of the NP-completeness of LOCAL-HAMILTONIAN involves testing whether or not a state satisfies local constraints imposed by simulating the evolution of a circuit.

In quantum information theory, constraints are generally presented as positive semi-definite "observable" operators, and satisfaction of all constraints amounts to the state being a ground-state for all such operators simultaneously. These "observables" correspond to events which can be measured and sampled using standard techniques. In quantum computation (as with probability distributions), constraint testing has imperfect soundness error, but soundness can at least be tested statistically provided many copies of the distribution.

I'll elaborate later; but the specific constraints which are tested for in the proof of QMA-completeness of LOCAL-HAMILTONIAN correspond precisely to whether the state of a system A before some unitary operation, corresponds to the state of the system A after the unitary operation, this being exactly what local checkability represents.

On this basis, provided that this is what you mean, I would say that quantum computation admits a notion of local checkability.