Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics

On the Complexity of Random Quantum Computations and the Jones Polynomial

Mick Bremner and I have just uploaded to arXiv our paper "On the Complexity of Random Quantum Computations and the Jones Polynomial". In this paper, we use the natural relationship between Jones polynomials and quantum computation to bound the classical complexity of approximately simulating random quantum computations, under plausible complexity-theoretic assumptions.

A random quantum computation is the action of:

  1. Preparing an initial state.
  2. Applying a randomly chosen unitary matrix.
  3. Measuring in the computational basis.
This is equivalent to sampling from a probability distribution \(\mathcal{D}_U\), where \(U\) is a randomly chosen unitary matrix.

Definition 1 (\(\mathcal{D}_U\))   For a \(d \times d\) unitary matrix \(U\), we define \(\mathcal{D}_U\) to be the probability distribution over integers \(x\in[d]\), given by $$\textbf{Pr}[x] := |\langle x | U | 0 \rangle|^2.$$

A natural choice of random unitary matrices would be those drawn from the uniform distribution. The uniform distribution over the unitary group \(\textrm{U}(d)\) is defined by the Haar measure, which is the unique translation-invariant measure on the group. Unfortunately, random unitary matrices drawn from the Haar measure cannot be implemented efficiently by a quantum computer.

Instead, we shall consider random unitary matrices drawn from an \(\epsilon\)-approximate unitary \(t\)-design, which can be implemented efficiently by a quantum computer. A unitary \(t\)-design is a distribution over a finite set of unitary matrices which imitates the properties of the Haar measure up to the \(t^{\mathrm{th}}\) moment. For convenience, let \(\mathrm{Hom}_{(t,t)}(\textrm{U}(d))\) be the set of polynomials homogeneous of degree \(t\) in the matrix elements of \(U\) and homogeneous of degree \(t\) in the matrix elements of \(U^*\).

Definition 2 (Unitary \(t\)-design)   A distribution \(\mathcal{D}=\{p_i, U_i\}\) over unitary matrices in dimension \(d\) is a unitary \(t\)-design if, for any polynomial \(f \in \mathrm{Hom}_{(t,t)}(\textrm{U}(d))\), $$\sum_{U_i \in \mathcal{D}}p_if(U_i) = \int\limits_{\textrm{U}(d)}f(U)dU.$$
Definition 3 (\(\epsilon\)-approximate unitary \(t\)-design)   A distribution \(\mathcal{D}=\{p_i, U_i\}\) over unitary matrices in dimension \(d\) is an \(\epsilon\)-approximate unitary \(t\)-design if, for any polynomial \(f \in \mathrm{Hom}_{(t,t)}(\textrm{U}(d))\), $$(1-\epsilon)\int\limits_{\textrm{U}(d)}f(U)dU \leq \sum_{U_i \in \mathcal{D}}p_if(U_i) \leq (1+\epsilon)\int\limits_{\textrm{U}(d)}f(U)dU.$$

We observe that these approximate unitary designs produce output probability distributions that satisfy the following anti-concentration bound.

Lemma 1   Let \(U\) be a \(d \times d\) unitary matrix distributed according to an \(\epsilon\)-approximate unitary \((t\geq2)\)-design, then, for any unit vectors \(|\alpha\rangle\), \(|\beta\rangle\) and a constant \(0 \leq \gamma \leq 1-\epsilon\), the following holds $$\underset{U}{\textbf{Pr}}\left[|\langle\alpha|U|\beta\rangle|^2>\frac{\gamma}{d}\right] \geq \frac{(1-\epsilon-\gamma)^2}{2(1+\epsilon)}.$$

This bound is used to prove that if there exists an efficient classical algorithm which can sample from these distributions up to a constant total variation distance, then Stockmeyer's Counting Theorem can be used to produce relative-error approximations to a constant fraction of their output probabilities.

Theorem 2   Let \(U\) be a \(d \times d\) unitary matrix distributed according to an \(\epsilon\)-approximate unitary \((t\geq2)\)-design and let \(\mathcal{D}_U\) be its corresponding probability distribution. Suppose that there is a classical polynomial-time algorithm \(C\), which, for any \(U\), samples from a probability distribution \(\mathcal{D}^\prime\), such that \(||\mathcal{D}^\prime-\mathcal{D}_U||_1 \leq \mu\). Then, for any \(\gamma\) such that \(0 < \gamma < 1-\epsilon\), there is an \(\textrm{FBPP}^{\textrm{NP}^C}\) algorithm which approximates \(|\langle0|U|0\rangle|^2\) up to a relative error \(\frac{4\mu(1+\epsilon)^2}{\gamma(1-\epsilon-\gamma)^2}+o(1)\) on at least a \(\frac{(1-\epsilon-\gamma)^2}{4(1+\epsilon)}\) fraction of matrices.

Theorem 2 tells us that, if there exists an efficient classical algorithm which can approximately sample from any random quantum computation, then, there is an \(\textrm{FBPP}^\textrm{NP}\) algorithm which can approximate \(|\langle0|U|0\rangle|^2\) up to a relative error for a fraction of matrices \(U\). Suppose that this algorithm solves a \(\textrm{#P-hard}\) problem, then, by Toda's Theorem, the Polynomial Hierarchy collapses to its third level.

We shall show that \(|\langle0|U|0\rangle|^2\) is proportional to the Jones polynomial of a random link, which is known to be \(\textrm{#P-hard}\) to compute up to a relative error in the worst-case.

Definition 4 (Jones polynomial)   The Jones polynomial \(V_L(\omega)\) is a link invariant, which assigns to each oriented link a Laurent polynomial in the variable \(\omega^{1/2}\).

We define random links via the braid group on \(2n\) strands \(B_{2n}\).

Definition 5 (Random braid)   A random braid on \(2n\) strands is generated by uniformly at random applying generators of the braid group. The length of a braid is the number of generators applied.
Definition 6 (Random link)   A random link is generated by the plat closure of a random braid.
Definition 7 (Plat closure)   The plat closure of a \(2n\)-strand braid \(b \in B_{2n}\) is the link formed by connecting pairs of adjacent strands on the left and the right of the braid. The link that is formed by the plat closure of the braid is often denoted \(b^{pl}\).

We relate braids and unitary matrices via the path model representation. For an integer \(k\), the \(k^{\mathrm{th}}\) path model representation gives a unitary representation of the braid group. In this representation, each braid \(b \in B_{2n}\) is mapped to a unitary matrix \(\rho_k(b)\). These unitary matrices have the property that the expectation value \(\langle0|\rho_k(b)|0\rangle\) is proportional, up to an efficiently computable factor, to the Jones polynomial \(V_{b^{pl}}(\exp(2\pi i/k))\) of the plat closure of \(b\). A beautiful result of Aharonov, Jones, and Landau showed that such representations can be implemented efficiently on a quantum computer. It is known that when \(k=5\) or \(k\geq7\) these representations are universal for quantum computation.

When combined with the results of Brandao, Harrow, and Horodecki on approximate unitary designs, it can be shown that in the \(k^{\mathrm{th}}\) path model representation with \(k=5\) or \(k\geq7\), random braids on \(2n\) strands of length \(\Omega[n(n+\log(1/\epsilon))]\) form an \(\epsilon\)-approximate unitary \(2\)-design

Theorem 3   In the \(k^{\mathrm{th}}\) path model representation with \(k=5\) or \(k\geq7\), there exists a constant \(\lambda>0\), such that random braids on \(2n\) strands of length $$\lambda n\left[n+\log(1/\epsilon)\right],$$ form an \(\epsilon\)-approximate unitary \(2\)-design.

We now relate the classical simulation of random quantum computations and the complexity of approximating the Jones polynomial of random links.

Theorem 4   Fix \(0<\epsilon<1\). Let \(k=5\) or \(k\geq7\) be an integer, and \(\omega=\exp(2\pi i/k)\) its corresponding root of unity. Let \(b \in B_{2n}\) be a random braid on \(2n\) strands of length \(\Omega\left[n(n+\log(1/\epsilon))\right]\). Let \(\rho_k(b)\) be the \(k^{\mathrm{th}}\) path model representation of \(b\), and let \(\mathcal{D}_{\rho_k(b)}\) be its corresponding probability distribution. Suppose that there is a classical polynomial-time algorithm \(C\), which, for any \(b\), samples from a probability distribution \(\mathcal{D}^\prime\), such that \(||\mathcal{D}^\prime-\mathcal{D}_{\rho(b)}||_1 \leq \mu\) and assume that Conjecture 1 holds. Then, there is a \(\textrm{BPP}^\textrm{NP}\) algorithm for solving any problem in \(\textrm{P}^\textrm{#P}\) and by Toda's Theorem the Polynomial Hierarchy collapses to its third level.

The proof of Theorem 4 follows directly from Theorem 2 and Theorem 3.

Conjecture 1   In the notation of Theorem 4. For some \(0<\gamma<1-\epsilon\), it is \(\textrm{#P-hard}\) to approximate the Jones polynomial \(V_{b^{pl}}(\omega)\) up to a relative error \(\frac{4\mu(1+\epsilon)^2}{\gamma(1-\epsilon-\gamma)^2}+o(1)\) on at least a \(\frac{(1-\epsilon-\gamma)^2}{4(1+\epsilon)}\) fraction of random braids.
Remark 1   It is worth noting that the \(5^{\mathrm{th}}\) path model representation is equivalent to the Fibonacci representation of the braid group. Therefore, our results extend to the random braiding of Fibonacci anyons.

Assuming that Conjecture 1 holds and the Polynomial Hierarchy does not collapse, Theorem 4 tells us that there is no efficient classical algorithm which can sample from any random quantum computation. This implies that random quantum computations can not be efficiently simulated by a classical computer.