Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics

Quantum Parameterized Complexity

Michael Bremner, Zhengfeng Ji, Luke Mathieson, Mauro Morales, Alexis Shaw, and I have just uploaded to arXiv our paper "Quantum Parameterized Complexity". In this paper we establish a quantum equivalent of classical parameterized complexity theory, motivated by the need to establish new tools for the complexity-theoretic classification of real-world problems. We introduce the quantum analogues of a range of parameterized complexity classes (see Table I), and examine the relationship between these classes, their classical counterparts, and well-studied problems (see Figure 1). In some cases, the quantum generalisations and their relationships follow almost directly from the equivalent classical definitions and their relationships. However, in other cases, the quantum generalisations are much less straightforward, for example, in the case of the quantum generalisation of the \(\text{W}\) hierarchy. This framework exposes a rich classification of the complexity of parameterized versions of \(\text{QMA-hard}\) problems, demonstrating, for example, a clear separation between the Quantum Circuit Satisfiability problem and the Local Hamiltonian problem.

Classical Class Quantum Class Description
\(\text{FPT}\) \(\text{FPQT}\) Fixed-Parameter Quantum Tractable.
\(\text{para-NP}\) \(\text{para-QMA}\) Parameterized Quantum Merlin Arthur.
\(\text{para-QCMA}\) Parameterized Quantum Classical Merlin Arthur.
\(\text{XP}\) \(\text{XQP}\) Slice-Wise Quantum Polynomial Time.
\(\text{W[P]}\) \(\text{QW[P]}\) FPQT reducible to Weight-\(k\) Quantum Circuit Satisfiability.
\(\text{QCW[P]}\) FPQT reducible to Classical Weight-\(k\) Quantum Circuit Satisfiability.
\(\text{W}[t]\) \(\text{QW}[t]\) FPQT reducible to Weight-\(k\) Weft-\(t\) Depth-\(d\) Quantum Circuit Satisfiability.
\(\text{QCW}[t]\) FPQT reducible to Classical Weight-\(k\) Weft-\(t\) Depth-\(d\) Quantum Circuit Satisfiability.
\(\text{QCW}_c[t]\) FPQT reducible to Hamming Weight-\(k\) Weft-\(t\) Depth-\(d\) Quantum Circuit Satisfiability.

Table 1:  Classical parameterized complexity classes and their quantum analogues.

We establish several structural results concerning quantum and classical parameterized complexity classes, for example, we show that \(\text{FPT}=\text{FPQT}\) if and only if \(\text{P}=\text{BQP}\). We also establish key technical components of quantum parameterized complexity such as FPQT reductions. Further, we apply the notion of fixed-parameter quantum tractability to the problem of approximate counting and approximating quantum circuit probability amplitudes.

Figure 1:  Complexity classes and problems discussed in the paper.

One of our most important observations concerns the complexity of weighted quantum Merlin Arthur problems, i.e., where the witness state is constrained to be a superposition of \(n\)-bit strings of Hamming weight \(k\). We show that the Weight-\(k\) Quantum Circuit Satisfiability problem is \(\text{QW[P]-complete}\) under FPQT reductions and the Weight-\(k\) \(l\)-Local Hamiltonian problem is in \(\text{XP}\).

Proposition 1   Weight-\(k\) Quantum Circuit Satisfiability is \(\text{QW[P]-complete}\) under FPQT reductions.
Proposition 2   Weight-\(k\) \(l\)-Local Hamiltonian is in \(\text{XP}\).

Since Weight-\(k\) Quantum Circuit Satisfiability cannot be in \(\text{XP}\) unless \(\text{P}=\text{BQP}\), this demonstrates a clear separation between the two problems.