Quantum hardness of XQUATH conjecture

Question

Consider the XQUATH conjectures, as defined here (https://arxiv.org/abs/1910.12085, Definition 1).

(XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There is no polynomial-time classical algorithm that takes as input a quantum circuit $C \leftarrow D$ and produces an estimate $p$ of $p_0$ = Pr[C outputs $|0^{n}\rangle$] such that \begin{equation} E[(p_0 − p)^{2}] = E[(p_0 − 2^{−n})^{2}] − Ω(2^{−3n}) \end{equation} where the expectations are taken over circuits $C$ as well as the algorithm’s internal randomness.

Here, $D$ is any distribution "over circuits on $n$ qubits that is unaffected by appending NOT gates to any subset of the qubits at the end of the circuit." For the purposes of our discussion, we can assume the circuit $C$ to be a particular Haar random unitary.

So, we believe the task mentioned in XQUATH is hard for classical computers. But how hard is the task for quantum computers? If it is easy for quantum computers, what is the algorithm?

A trivial algorithm I can think of just runs the quantum circuit many times, samples from the output distribution of the circuit each time, and then computes the frequency of observing $|0^{n}\rangle$. But what is the guarantee that this procedure will give us an additive error estimate robust enough to meet the condition of XQUATH?

Answer 1

Maybe think of it this way - a quantum computer, executing a small enough random circuit $C$ acting on a state initially prepared as $\vert 0^n\rangle$ and sampling therefrom, will get an $n$-bit string as output, say $0110\cdots10$. We know, merely from the fact that this was sampled, that the squared amplitude of $\vert 0110\cdots10\rangle$ is large and likely contributes more than $1/2^n$ to the linear cross-entropy score.

I think the implications of the XQUATH conjecture are that a classical computer likely cannot even determine the output probability of even the all-zeroes basis vector $\vert 0000\cdots 00\rangle$, much less any particular vector such as $\vert 0110\cdots10\rangle$. The all-zeroes vector was chosen as both the input vector (the initially prepared state) and the output vector (the state with which the squared amplitudes are calculated) only for convenience, and as you note you could always append $\mathsf{NOT}$ gates to the output circuit without changing the analysis.

If we execute a circuit $C$ and output the string $0110\cdots10$, we can think of another circuit $C'$ wherein we append a $\mathsf{NOT}$ gate onto the second, third, ..., second-to-last bit, and the conjecture goes through.

That is, it appears that Aaronson and Gunn conjecture that it's classically hard to determine an output probability of any particular basis vector, which would be needed to spoof the cross-entropy score. But quantumly all we need to do is execute the circuit and sample therefrom.

Answer 2

Usually, the complexity to compute output probabilities from quantum circuit sampling (considering that depth and number of gates is in poly($n$) obviously) depend on the number of samples required to be "relevent" enough for a specific test, it being XEB in the case of XQUATH. So if the required number of sample $M$ is in $poly(n)$, and is enough to compare classical and quantum under a specific test, the quantum algorithm is efficient. This refers basically at the "scallability" of quantum supremacy experiment.

The bottom line being that the guarantie that XQUATH is easy for a quantum algorithm is that it's corresponding circuit is "not too noisy" (UPDATE :noisy circuit are $2^{-\Theta(d)}$ close to uniform, see https://arxiv.org/abs/2112.00716, this paper actually raised strong doubts on XQUATH), and the experiment size is polynomial in the number of qubits.