Sum Over Paths: the Feynman View of Circuits
Every circuit amplitude is a sum over computational paths.
Insert a resolution of the identity between every pair of gates and a circuit becomes an exponentially long sum of trivial terms. For Hadamard-plus-diagonal circuits each term is , and an amplitude is a signed count of the zeros of a cubic polynomial over . That single identity puts BQP inside PP and draws the line between Clifford ease and universal hardness.
What you’ll learn
- State and prove the path-sum expansion, and analyze it as a polynomial-space simulation algorithm.
- Derive the phase-polynomial form for circuits over .
- Prove from the path sum using closure properties of GapP.
- Explain why quadratic (Clifford) path sums are efficiently computable while cubic ones are #P-hard.
The Feynman expansion as an algorithm
The proof is insertions of . The content is in the cost. Schrödinger-style simulation stores the state: time , memory . Feynman-style simulation walks the paths depth-first and keeps only the current one: memory polynomial in and , time exponential. Halving the circuit recursively interpolates between the two.
Split the circuit at its midpoint and sum over the middle basis state.
Each of the terms needs two half-length amplitudes, computed recursively.
Unroll the recursion: time , i.e. for depth .
Each recursion level stores one -bit and one running sum of polynomial precision, and the space is reused across terms.
Summing over one at a time keeps polynomial space, so acceptance probabilities of polynomial-size circuits are computable in PSPACE. (This poly-space, -time trade-off is analyzed by Aaronson and Chen, 2017.)
Compared with state-vector simulation, what does the Feynman path-sum simulation of an -qubit, -gate circuit save?
- Memory: instead of
- Time: polynomial instead of exponential
- Both time and memory
- Nothing: it is only a conceptual tool
Show the answer
A. Memory: instead of
Depth-first summation stores only the current path (or, with halving, basis states), so memory is polynomial. The number of paths is still exponential, so time stays exponential.
Hadamards make variables, diagonal gates make phases
Restrict to the gate set ; it is universal for BQP because is (Shi 2003; Aharonov 2003) and Toffoli . CNOT is likewise , CZ, . Now label every wire value by a Boolean expression and read the circuit left to right.
Input wires carry the constants . Each Hadamard creates a fresh path variable on its wire: .
Diagonal gates multiply each path by a sign that is a monomial in the current labels; only relabels.
Collect the factors. Here is the number of Hadamards, is the sum of all the monomials, and is the final label of wire .
Each constraint fixes one variable (or is a constant that kills the amplitude). Substituting leaves a free sum over variables. Here .
For , the theorem gives . What is , in percent?
Show the answer
56 %
only at , so and the amplitude is . Hence . For the amplitude is , and .
BQP ⊆ PP, and the Clifford boundary
Squaring an amplitude doubles the path variables: a probability is a sum over pairs of paths.
is polynomial-time computable, so , the class of differences of two #P functions.
GapP contains polynomial-time integer functions and is closed under subtraction and multiplication by constants (Fenner, Fortnow & Kurtz 1994).
The bounded-error promise becomes a sign condition.
Finally, , so .
Now look at the degree. Without CCZ (and with gates allowed, which turn the phase into a -valued quadratic form) the circuit is Clifford, and exponential sums of quadratic forms are computable in polynomial time. Over this is Dickson's classification: a quadratic in variables has
where is the (even) rank of the alternating form . So Clifford amplitudes are or times a power of : interference is all-or-nothing on a dyadic scale. This is the path-sum face of the Gottesman–Knill theorem (compare Dehaene and De Moor, 2003). One CCZ raises the degree to 3, and computing gaps of cubics is #P-hard.
A circuit over has a phase polynomial of degree . Which values can take?
- Any real number in
- Only or
- Only
- Only or for some integer
Show the answer
D. Only or for some integer
The amplitude is with , giving or . For instance has amplitudes and has and .
From circuits to the path integral, and the frontier
The name is not a metaphor. For a particle with Hamiltonian , split into short steps (trotterization), insert position resolutions between them and integrate out the momenta: as ,
Paths near a stationary point of the action add in phase, while the rest cancel among themselves. Classical mechanics () emerges as constructive interference, the continuum version of .
Key takeaways
- : exponentially many terms, each trivial, computable in polynomial space.
- For circuits, amplitudes are for a polynomial of degree over .
- Probabilities are signed sums over pairs of paths, i.e. GapP functions; this gives (indeed ).
- Degree 2 (Clifford) gaps are easy, ; degree 3 is #P-hard. The simulability boundary is visible in the phase polynomial.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
For , what is ?
Show the answer
C.
Group by Hamming weight: , so the amplitude is . Without the cubic term the sum would be ; the single flipped term at shifts it by .
In the proof of , the acceptance probability becomes a sum over twice as many path variables as an amplitude. Why?
- Because each Hadamard must be counted twice for normalization
- Because : a probability is a sum over pairs of paths
- Because PP machines need two witnesses per accepting path
- Because measurement adds one variable per qubit
Show the answer
B. Because : a probability is a sum over pairs of paths
Probabilities are quadratic in amplitudes. Expanding the square writes as a single signed sum over pairs , a GapP quantity, which is what PP can threshold.
Why does the path-sum formula not make Clifford circuits #P-hard to simulate?
- Clifford circuits have only polynomially many paths
- Clifford circuits contain no Hadamard gates
- Their phase polynomials are quadratic, and signed counts of quadratic forms are computable in polynomial time
- Their amplitudes are always or
Show the answer
C. Their phase polynomials are quadratic, and signed counts of quadratic forms are computable in polynomial time
Clifford circuits still have exponentially many paths, but their phase is a quadratic form, and Dickson-type reductions evaluate efficiently. Degree 3 (one CCZ type) is where #P-hardness begins.
Further reading
- R. P. Feynman, "Space-time approach to non-relativistic quantum mechanics", Rev. Mod. Phys. 20, 367 (1948).
- E. Bernstein & U. Vazirani, "Quantum complexity theory", SIAM J. Comput. 26, 1411 (1997).
- L. M. Adleman, J. DeMarrais & M.-D. A. Huang, "Quantum computability", SIAM J. Comput. 26, 1524 (1997).
- C. M. Dawson, H. L. Haselgrove, A. P. Hines, D. Mortimer, M. A. Nielsen & T. J. Osborne, "Quantum computing and polynomial equations over the finite field ", Quantum Information & Computation (2005).
- A. Montanaro, "Quantum circuits and low-degree polynomials over ", J. Phys. A (2017).