Quantum nonexpander problem is quantum-Merlin-Arthur-complete

A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that the problem of deciding whether a quantum channel is not rapidly mixing is a complete problem for the quantum Merlin-Arthur complexity class. This has applications to testing randomized constructions of quantum expanders and studying thermalization of open quantum systems.

Figure 1

Hadamard test for $V_{d,e}$.

Figure 2

A controlled expander, $\Lambda \mathcal{F}$.

Figure 3

The map $\Phi$ constructed from the verifier circuit $V$, the complete depolarizer $\mathcal{D}$, and the ${\kappa }_{\mathcal{E}}$-contractive expander $\mathcal{E}$. The first controlled depolarizer is applied only if the ancillae are not all zero and the second one only if the top output is zero. The controlled $\mathcal{E}$ expander is applied only if the bottom qubit is one. Note that this figure is not a true circuit because $\mathcal{D}$ and $\mathcal{E}$ are quantum expanders, not unitary gates.

Figure 4

The controlled expander verifying the ancillae. The unitary $W$ is selected from $\{\mathbb{1},\mathrm{X},\mathrm{Y},\mathrm{Z},-\mathbb{1},-\mathrm{X},-\mathrm{Y},-\mathrm{Z}\}$ uniformly at random.