Consider the Feynman algorithm for simulating quantum circuits, as given here.
Consider the XQUATH conjecture for random quantum circuits from here, given by
(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.
It is mentioned in the paper that the Feynman method comes close to spoofing XQUATH. The authors remark:
The simplest way to attempt to refute XQUATH might be to try $k$ random Feynman paths of the circuit, all of which terminate at $|0^{n} \rangle$, and take the empirical mean over their contributions to the amplitude.
Does this yield a polynomial time algorithm though? What is the time taken to compute each Feynman path? Assume that each gate is acts non trivially on at most two qubits.
On a related note, the wikipedia link, it is mentioned that the Feynman algorithm, in general, takes $4^{m}$ time and $(m+n)$ space --- I do not see why that is so.
