When to use BGLS

As discused in the Getting started guide, you can use BGLS with different representations of quantum states (state vectors, density matrices, tensor networks, etc.), functions to apply operations to these states, and functions to compute probabilities from these states - but when should you use BGLS?

The short answer

Relative to the usual qubit by qubit sampling algorithm, you should use BGLS when its easier to compute probabilities than it is to compute marginal distributions. This is generally true for memory-limited cases when you cannot store the entire statevector in classical memory, for example with Clifford states and matrix product states. Read below to see a summary of Bravyi, Gosset, and Liu’s argument for why this is true.

Understanding the cost

In both qubit-by-qubit sampling and BGLS gate-by-gate sampling, the state is evolved in the same manner. The difference is that BGLS computes a set of probabilities during state evolution to sample bitstrings, whereas qubit-by-qubit sampling computes marginal distributions from the final state.

BGLS gate-by-gate sampling

How many probabilities do you need to compute during state evolution for BGLS? For an operation \(U_t\), you need to compute \(2^{\text{supp}(U_t)}\) probabilities where \(\text{supp}(U_t)\) (the support of \(U_t\)) is the number of qubits that \(U_t\) acts on. So for a depth \(d\) circuit \(U := U_d \cdots U_1\) you need to compute \(\sum_{t = 1}^{d} 2^{\text{supp}(U_t)}\) probabilities. This quantity is upper bounded by \(d 2^k\) where \(k = \max_t \text{supp}(U_t)\). Letting \(f(n, d)\) denote the cost of computing an amplitude (probability) from a depth \(d\), \(n\)-qubit circuit, the cost of BGLS gate-by-gate sampling is thus at most \(d 2^k f(n, d)\).

Qubit-by-qubit sampling

Marginal distributions have the form \(\langle 0 | U^\dagger (|x \rangle \langle x| \otimes I) U | 0 \rangle\), so we expect computing a marginal distribution to have a cost comparable to \(f(n, 2d)\). Assuming we sample \(n\)-bit strings the cost qubit-by-qubit sampling is thus \(n f(n, 2d)\).

The cost ratio

From the above, we can generally say that it makes sense to use BGLS when \(r := n f(n, 2d) / d 2^k f(n, d)\) is large.

For Schrodinger simulation (full statevector simulation), we have that \(f(n, d) \sim n d 2^n\). In this case \(r \sim 2n / d 2^k\).

For Feynman simulation (sum over paths), we have that \(f(n, d) \sim n (2d)^{n + 1}\). In this case \(r \sim n 2^n / d 2 ^k\). Unlike the Schrodinger simulation case above, the ratio now grows exponentially in \(n\) and the advantage of BGLS is significant.

Examples

Refer to the examples, including Clifford states and matrix product states, for specific illustrations of when using BGLS is advantageous.