What's the notion of input size for Quantum Verification?

Question

I've been looking into $\mathsf{QPIP}_\tau$ as a complexity class. The following will be a summary of definition 3.12 in Classical Verification of Quantum Computations by Urmila Mahadev.

A language $L$ is said to have a Quantum Prover Interactive Proof ($\mathsf{QPIP}_\tau$ ) with completeness $c$ and soundness $s$ (where $c − s$ is at least a constant) if there exists a pair of algorithms $(P, V)$, where $P$ is the prover and $V$ is the verifier, with the following properties:

1. The prover $P$ is a $\mathsf{BQP}$ machine, which also has access to a quantum channel which can transmit $\tau$ qubits.

2. The verifier $V$ is a hybrid quantum-classical machine. Its classical part is a $\mathsf{BPP}$ machine. The quantum part is a register of $\tau$ qubits, on which the verifier can perform arbitrary quantum operations and which has access to a quantum channel which can transmit $\tau$ qubits. At any given time, the verifier is not allowed to possess more than $\tau$ qubits. The interaction between the quantum and classical parts of the verifier is the usual one: the classical part controls which operations are to be performed on the quantum register, and outcomes of measurements of the quantum register can be used as input to the classical machine.

3. There is also a classical communication channel between the prover and the verifier, which can transmit polynomially many bits at any step.

4. At any given step, either the verifier or the prover perform computations on their registers and send bits and qubits through the relevant channels to the other party.

There are some more details regarding defining $c$ and $s$, but these are unimportant for my question. Additionally, it should suffice to take $\tau = 0$, and let $V$ be a $\mathsf{BPP}$ machine that has entirely classical communication with $P$.

---

I'm curious about how specifically the classical part of $V$ is supposed to manipulate the input. The setting for this paper is taking arbitrary $L\in\mathsf{BQP}$ and reducing it to 2-Local Hamiltonian (where the non-identity parts are Pauli $X$ and $Z$ gates), which is $\mathsf{QMA}$-complete. This means that the initial input $L$ is specified as some polynomial-size quantum circuit, which must be reduced (in quantum polynomial time) to a local hamiltonian instance.

I have issues understanding how $V$ (in the case when $\tau = 0$, so $V$ is just a $\mathsf{BPP}$ machine) can preform this reduction, or even more generally hold the quantum circuit. Each of the (polynomially many) gates in the circuit is a quantum gate, which for a $n$-qubit system would be of size $2^n\times 2^n$. I feel like $V$ can't have an input of this size, because then the input size is exponential in $n$ (which would cause all sorts of issues with restricting $V$ to be poly-time in the input).

I could see each of (polynomial many) gates $U_i$ being written as a product of (polynomial many) universal gates from some fixed, finite set of gates (or even some gate set of size $\mathsf{poly}(n)$ --- it shouldn't matter). This would mean that the input to $V$ is small enough such that "polynomial time in the input" is a reasonable restriction.

1. Under such a restriction, can a $\mathsf{BPP}$ verifier $V$ reduce the circuit $L$ to $2$-Local Hamiltonian?

2. Additionally, while such a restriction is natural to me, is this how it is typically done? Specifically, how are quantum circuits generally input to classical machines?

Answer 1

The answer is yes to both questions. See page 2 of Bookatz's QMA-Complete Problems, which states:

When a problem is given a unitary or quantum circuit, $U_x$, it is assumed that the problem is actually given a classical description $x$ of the corresponding quantum circuit, which consists of $\mathsf{poly}(|x|)$ elementary gates. Likewise, quantum channels are specified by efficient classical description.

So the input to $V$ is entirely classical, and polynomial-sized in $|x|$, which is usually taken to be the input to the circuit (and therefore the number of qubits).

As for a verifier being able to reduce things to 2 local Hamiltonian, this is also yes. This picture is from 3-Local Hamiltonian is QMA Complete, and constructs a 3-Local Hamiltonian entirely from projections and $U_i$'s. As the various $U_i$'s are efficiently representable classically (and I assume projections onto the computational basis are as well), it appears a $\mathsf{P}$ machine should be able to construct the local Hamiltonian efficiently (given the classical description of $U_x$, likely with respect to a fixed universal gate set).

Note that the below construction is for 3 Local Hamiltonian, and while the construction for 2 Local Hamiltonian is more technical, I see no difficulties in extending the above argument.