Quantum hardness of XQUATH conjecture

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 $$$$E[(p_0 − p)^{2}] = E[(p_0 − 2^{−n})^{2}] − Ω(2^{−3n})$$$$ 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?

• I'm not sure but I think $\vert 0^n\rangle$ is a stand-in for any dummy output, and the XQUATH problem is more akin to "there's no efficient classical algorithm to estimate a particular output probability. " There is nonetheless a quantum algorithm that will give evidence that a particular output/basis has a probability strictly greater than $1/2^n$ namely, just execute the circuit $C$, and whatever output you get has decent odds of being sampled (greater than $1/2^n$. Apr 8 at 23:39
• But doesn’t the paper strictly talk about estimating the probability of $|0^{n}\rangle$? Apr 9 at 5:33
• Referring to page 2: "Informally, QUATH states that it is impossible for a polynomial-time classical algorithm to guess whether a specific output string like $\vert 0^n\rangle$ has greater-than-median probability of being observed as the output of a given n-qubit quantum circuit". Also, the abstract notes "outputting a specific output string, say $\vert 0^n\rangle$, with mean squared error even slightly better than that of the trivial estimator that always estimates $1/2^n$." That is, it appears that $\vert 0^n\rangle$ is just a dummy output chosen for convenience. Apr 9 at 15:24

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.