The hybrid Schrödinger-Feynman algorithm (in the quantum supremacy experiment)

[Philip Thrift]

https://arxiv.org/abs/1807.10749 :

Quantum Supremacy Is Both Closer and Farther than It Appears

Our algorithms can be characterized as Schrödinger-Feynman hybrids.

Our simulator combines highly-optimized Schrödinger-style simulation within each

qubit block and simulates xCZ gates with Feynman-style path summation, to limit memory use. Unlike in Feynman-style simulation, runtime scales with the number of xCZ gates, which is very limited in planar qubitarray architectures with nearest-neighbor gates. Unlike traditional Schrödinger-style simulation, the resulting algorithms are depth-limited, and supercomputer simulations may hold some advantage for very deep circuits. However, near-term quantum computers rely on noisy gates that also limit circuit depth.

https://phsites.technion.ac.il/qst2019/wp-content/uploads/sites/50/2019/09/Pedram_Roushan_Lecture3_Supramacy_Technion_Summer_School_20191.pdf :

Lecture 3: The Quantum Supremacy Experiment

Two basic approaches to such simulation are provided by the Schrödinger and Feynman algorithms. In the former, the classical computer stores the full wavefunction in memory and propagates it under the evolution induced by the quantum circuit. The memory required to store the full wavefunction of n qubits scales exponentially in n and for a 47-qubit system reaches about a petabyte which is at the limit of the most powerful classical supercomputers.

In practice, one does not need to compute all 2^n amplitudes since for large n only a small fraction of the output bitstrings can be observed in any given experiment. Feynman algorithm computes a single output amplitude by summing the contributions from all Feynman paths and uses only polynomial amount of memory. However, its runtime scales exponentially in the number of gate cycles m (roughly proportional to the evolution time). There are intermediate approaches that combine ideas from both algorithms and enable classical simulation for moderate values of n and m which in practice are too large for both Schrödinger and Feynman algorithms. However,

all known high fidelity classical algorithms for the simulation of RQCs with gates from a universal set require resources exponential in n, m or both. The non-existence of polynomial algorithms suggests that sampling from the output probabilities of universal RQCs (random quantum circuits) constitutes a viable approach to demonstrating quantum supremacy.

http://www.spaceref.com/news/viewsr.html?pid=52862 :

Quantum Supremacy Using a Programmable Superconducting Processor

Note: this paper was originally posted on NASA NTRS but was then removed, NASA has not provided a reason for its removal.

We use a hybrid Schrödinger-Feynman algorithm (SFA) running on Google data centers to compute the amplitudes of individual bitstrings. This algorithm breaks the circuit up into two patches of qubits and efficiently simulates each patch using a Schrodinger method, before connecting them using an approach reminiscent of the Feynman path-integral. 

While it is more memory efficient, SFA becomes exponentially more computationally expensive with increasing circuit depth due to the exponential growth of paths with the number of gates connecting the patches.

On the Summit supercomputer, which is currently the most powerful in the world, we used a method inspired by Feynman path integrals that is most efficient at low depth

@philipthrift