# Feynman method and polynomial time algorithm for XQUATH

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 $$$$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.

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.