11
$\begingroup$

There are many fairly standard quantum algorithms that can all be understood within a very similar framework, from Deutsch's algorithm Simon's problem, Grover's search, Shor's algorithm and so on.

One algorithm that seems to be completely different is the algorithm for evaluating the Jones Polynomial. Moreover, it seems like this is a crucial algorithm to understand in the sense that it is a BQP-complete problem: it exhibits the full power of a quantum computer. Also, for a variant of the problem, it's DQC-1 complete, i.e. it exhibits the full power of one clean qubit.

The Jones Polynomial algorithm paper presents the algorithm in a very different way to the other quantum algorithms. Is there a more similar/familiar way that I can understand the algorithm (specifically, the unitary $U$ in the DQC-1 variant, or just the whole circuit in the BQP-complete variant)?

$\endgroup$
3
+100
$\begingroup$

This answer is more or less a summary of the Aharonov-Jones-Landau paper you linked to, but with everything not directly related to defining the algorithm removed. Hopefully this is useful.

The Aharonov-Jones-Landau algorithm approximates the Jones polynomial of the plat closure of a braid $\sigma$ at a $k$th root of unity by realizing it as (some rescaling of) a matrix element of a certain unitary matrix $U_\sigma$, the image of $\sigma$ under a certain unitary representation of the braid group $B_{2n}$. Given an implementation of $U_\sigma$ as a quantum circuit, approximating its matrix elements is straightforward using the Hadamard test. The nontrivial part is approximating $U_\sigma$ as a quantum circuit.

If $\sigma$ is a braid on $2n$ strands with $m$ crossings, we can write $\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$, where $a_1, a_2, \ldots, a_m \in \{1, 2, \ldots, 2n - 1\}$, $\epsilon_1, \epsilon_2, \ldots, \epsilon_m \in \{\pm 1\}$, and $\sigma_i$ is the generator of $B_{2n}$ that corresponds to crossing the $i$th strand over the $(i + 1)$st. It suffices to describe $U_{\sigma_i}$, since $U_\sigma = U_{\sigma_{a_1}}^{\epsilon_1} \cdots U_{\sigma_{a_m}}^{\epsilon_m}$.

To define $U_{\sigma_i}$, we first give a certain subset of the standard basis of $\mathbb{C}^{2^{2n}}$ on which $U_{\sigma_i}$ acts nontrivially. For $\psi = \lvert b_1 b_2 \cdots b_{2n} \rangle$, let $\ell_{i'}(\psi) = 1 + \sum_{j = 1}^{i'} (-1)^{1-b_j}$. Let's call $\psi$ admissible if $1 \leq \ell_{i'}(\psi) \leq k - 1$ for all $i' \in \{1, 2, \ldots, 2n\}$. (This corresponds to $\psi$ describing a path of length $2n$ on the graph $G_k$ defined in the AJL paper.) Let $$\lambda_r = \begin{cases}\sin(\pi r / k) & \textrm{if $1 \leq r \leq k - 1$},\\ 0 & \textrm{otherwise.}\end{cases}$$ Let $A = ie^{-\pi i/2k}$ (this is mistyped in the AJL paper; also note that here and only here, $i = \sqrt{-1}$ is not the index $i$). Write $\psi = \lvert \psi_i b_i b_{i+1} \cdots\rangle$, where $\psi_i$ is the first $i - 1$ bits of $\psi$, and let $z_i = \ell_{i-1}(\psi_i)$. Then $$ \begin{align} U_{\sigma_i}(\lvert\psi_i 00 \cdots\rangle) & = A^{-1}\lvert\psi_i 00 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 01 \cdots \rangle) & = \left( A\frac{\lambda_{z_i-1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 01 \cdots\rangle + A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 10 \cdots \rangle) & = A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 01 \cdots\rangle + \left(A\frac{\lambda_{z_i+1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 11 \cdots\rangle) & = A^{-1}\lvert\psi_i 11 \cdots\rangle \end{align} $$ We define $U_{\sigma_i}(\psi) = \psi$ for non-admissible basis elements $\psi$.

We would now like to describe $U_{\sigma_i}$ as a quantum circuit with polynomially many (in $n$ and $k$) gates. Notice that while $U_{\sigma_i}$ only changes two qubits, it also depends on the first $i - 1$ qubits through the dependence on $z_i$ (and indeed, it depends on all qubits for the admissibility requirement). However, we can run a counter to calculate and store $z_i$ (and also determine admissibility of the input) in logarithmically many (in $k$) ancilla qubits, and therefore we can apply the Solovay-Kitaev algorithm to get a good approximation to $U_{\sigma_i}$ using only polynomially many gates. (The paper appeals to Solovay-Kitaev twice: once for incrementing the counter at each step, and once for applying $U_{\sigma_i}$; I'm not sure if there is a more direct way to describe either of these as quantum circuits with standard gates. The paper also doesn't mention the need to check for admissibility here; I'm not sure if this is important, but certainly we at least need $1 \leq z_i \leq k - 1$.)

So to recap:

  1. Start with a braid $\sigma \in B_{2n}$ with $m$ crossings.
  2. Write $\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$.
  3. For each $i \in \{1, 2, \ldots, m\}$, apply the Solovay-Kitaev algorithm to get an approximation of the unitary matrix $U_{\sigma_{a_i}}$ (or its inverse if $\epsilon_i = -1$).
  4. Compose all of the approximations from step 3 to get a quantum circuit with polynomially many gates that approximates $U_{\sigma}$.
  5. Apply the real and imaginary Hadamard tests polynomially many times with the circuit from step 4 and the state $\lvert 1010 \cdots 10\rangle$.
  6. Average the results of step 5 and multiply by some scaling factor to get an approximation to the real and imaginary parts of the Jones polynomial of the plat closure of $\sigma$ evaluated at $e^{2\pi i/k}$.
$\endgroup$
2
$\begingroup$

You have mentioned five papers in the question, but one paper that remains unmentioned is the experimental implementation in 2009. Here you will find the actual circuit that was used to evaluate a Jones polynomial:

enter image description here

This might be the closest you will get to a "more familiar" presentation of the algorithm, as interest in the Jones polynomial and in DQC-1 have decayed a bit since 2009.

More details on this experiment can be found in Gina Passante's thesis.

$\endgroup$
  • 1
    $\begingroup$ I was unaware of that paper, thank you, although I was more specifically interested in the BQP-complete version. Equally, in my brief skim, I don't see much explanation about what the unitary $U_n$ actually is. $\endgroup$ – DaftWullie Jun 11 '18 at 18:04
  • $\begingroup$ You're welcome. Yes this was a 4-page PRL with details not explained as thoroughly as I'd like -- maybe there's a "Supplementary Material" on the journal's webpage that explains the U better. The Jones polynomial and DQC-1 were popular around 2008-2009 but I've stopped hearing about it since then. $\endgroup$ – user1271772 Jun 11 '18 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.