User:AKChapman/sandbox

LOQC (complexity)

In computational complexity theory, LOQC (linear optics quantum computation) is the class of decision problems solvable in polynomial time by a computer that can efficiently sample from a probability distribution produced by a linear-optical quantum network - that is, an arrangement of beam splitters and phase shifters that preserves quantum coherence. Because photons cannot interact in this model, it is not believed to be universal for quantum or even classical computation. However, the question of whether or not simulation of this model is a classically tractable task remains open. For instance, it has been demonstrated that there exist problems within this class that a classical computer may not be able to solve efficiently, such as the additive approximation of permanents of matrices with complex-valued entries, which is known to be #P-complete. An affirmative answer to this question would thus imply a collapse of the polynomial hierarchy at the third level. Furthermore, thanks to a construction by Knill, Laflamme, and Milburn, it is known that this model with the additional freedom of postselection is equivalent to universal quantum computation (formally, PostLOQC = BQP). As a result, this class is of growing interest to the quantum information community, as it arguably represents the most experimentally realistic model of quantum computation to-date.

Boson Sampling Model

File:GaltonBoard.gif

Galton's board, a simple classical analogy to the boson sampling model

When talking about linear optical networks, it is convenient to abstract away the individual photons' polarization degrees of freedom and instead only consider a model of non-interacting spin-less bosons. A network consists of an arrangement of beam splitters and phase shifters on $m$ modes, which may individually contain any number of bosons, though the total number of bosons in the network will remain fixed. To generate probability distributions, a configuration of $n\leq m$ bosons is input into the network, and the number of bosons in each mode is counted at the end. Running the circuit many times on the same input gives a probability distribution over the output photon number configurations.

The model is analogous to Galton's board, whereby balls are dropped onto an arrangement of pegs, at each of which the ball scatters randomly into one of two directions, generating a configuration of balls in the slots at the bottom. Here, the balls correspond to individual bosons, and the pegs correspond to optical elements. The problem of interest is encoded in the arrangement of pegs, and the output probability distribution is approximated by the configuration of balls at the bottom. There are however several crucial differences. The first is that the LOQC network is quantum, so each optical element coherently transfers a boson into a superposition of modes as opposed to sending it into one mode or the other. The second is that, in the LOQC model, we are allowed multiple input ports, as opposed to just one. Finally, the resulting probability distribution in the LOQC model is over the possible output configurations of bosons, whereas that in the Galton's board picture is over the possible slots in which the ball could end up. One run of the LOQC experiment - which may involve multiple bosons sent through the network simultaneously - thus corresponds to dropping just one ball through the Galton's board.

Formally, the Hilbert space of mode $i$ is spanned by the number states $|0\rangle _{i},|1\rangle _{i},|2\rangle _{i}$, etc. Beam splitters and phase shifters on the the joint state $|i_{1},i_{2},\dots ,i_{m}\rangle$ of all $m$ modes are generated by the following contributions to the Hamiltonian

${\begin{aligned}{\begin{cases}{\hat {n}}^{(i)}={\hat {a}}^{(i)\dagger }{\hat {a}}^{(i)}&{\rm {for\ phase\ shifters}}\\{\hat {b}}^{(ij)}={\hat {a}}^{(i)}{\hat {a}}^{(j)\dagger }+{\hat {a}}^{(i)\dagger }{\hat {a}}^{(j)}&{\rm {for\ beam\ splitters}}\end{cases}}\end{aligned}}$

where ${\hat {a}}^{(i)(\dagger )}$ are the bosonic ladder operators on the $i$th mode. Notice that both ${\hat {n}}^{(i)}$ and ${\hat {b}}^{(ij)}$ conserve boson number. It is thus more convenient to consider the actions of unitaries on creation operators rather than directly on the state, as

${\begin{aligned}{\hat {U}}{\hat {a}}^{(i)\dagger }|{\vec {0}}\rangle ={\hat {U}}{\hat {a}}^{(i)\dagger }{\hat {U}}^{\dagger }|{\vec {0}}\rangle =\sum _{j}(\mathbf {\Lambda } )_{ij}{\hat {a}}^{(j)\dagger }|{\vec {0}}\rangle \end{aligned}}$

where $|{\vec {0}}\rangle$ is the state with vacuum in each mode, and $\mathbf {\Lambda }$ is another unitary matrix related to ${\hat {U}}$ via homomorphism (see "Relationship to the permanent"), which acts on the set of modes as opposed to the the photon configuration states. The fact that ${\hat {U}}$ conserves photon number is crucial here. To obtain the first equality, we used the fact that the only state with zero photons in each mode is $|{\vec {0}}\rangle$, so $|{\vec {0}}\rangle ={\hat {U}}^{\dagger }|{\vec {0}}\rangle$, and the second equality comes from the fact that ${\hat {U}}^{\dagger }$ unitarily maps between different configurations with fixed total photon number. By inserting identities ${\hat {U^{\dagger }}}{\hat {U}}$, we may generalize this to a configuration of $n$ bosons ($n_{1}$ in the first mode, $n_{2}$ in the second mode, etc., such that $n_{1}+n_{2}+\dots +n_{m}=n$) as

${\begin{aligned}{\hat {U}}\prod _{i=1}^{m}({\hat {a}}^{(i)\dagger })^{n_{i}}|{\vec {0}}\rangle =\prod _{i=1}^{m}{\frac {1}{\sqrt {n_{i}!}}}\left(\sum _{j_{i}=1}^{m}(\mathbf {\Lambda } )_{ij_{i}}{\hat {a}}^{(j_{i})\dagger }\right)^{n_{i}}|{\vec {0}}\rangle \end{aligned}}\,$ 1

That is, ${\hat {U}}$ acts on each of the individual creation operators.

Known Results

Relationship to the Permanent

The permanent arises as a natural element of the homomorphism between the ${\hat {U}}$ and the $\mathbf {\Lambda }$. Let $\mathbf {\Lambda } _{[s_{1},s_{2},\dots ,s_{m}][t_{1},t_{2},\dots ,t_{m}]}$, where $s_{1}+s_{2}+\dots +s_{m}=t_{1}+t_{2}+\dots +t_{m}=n$, be a matrix of $s_{1}$ copies of the first row of $\mathbf {\Lambda }$, $s_{2}$ copies of the second row, etc., and $t_{1}$ copies of the first column of $\mathbf {\Lambda }$, $t_{2}$ copies of the second column, etc. One valid definition of $\mathbf {\Lambda }$ is such that

$\langle s_{1},s_{2},\dots ,s_{m}|{\hat {U}}|t_{1},t_{2},\dots ,t_{m}\rangle ={\frac {\rm {{Per(}\mathbf {\Lambda } _{[s_{1},s_{2},\dots ,s_{m}][t_{1},t_{2},\dots ,t_{m}]}{\rm {)}}}}{\sqrt {s_{1}!s_{2}!\dots s_{m}!t_{1}!t_{2}!\dots t_{m}!}}}$

so computing a given circuit amplitude is no harder than computing the permanent of the associated matrix $\mathbf {\Lambda } _{[s_{1},s_{2},\dots ,s_{m}][t_{1},t_{2},\dots ,t_{m}]}$. We check the above formula for $s_{1}=s_{2}=\dots =s_{m}=t_{1}=t_{2}=\dots =t_{m}=1$ using equation (1), as

${\begin{aligned}\langle 11\dots 1|{\hat {U}}|11\dots 1\rangle &=\langle 11\dots 1|\prod _{i=1}^{m}\sum _{j_{i}=1}^{m}(\mathbf {\Lambda } )_{ij_{i}}{\hat {a}}^{(j_{i})\dagger }|{\vec {0}}\rangle \\&=\sum _{\sigma \in S_{m}}\prod _{i=1}^{m}(\mathbf {\Lambda } )_{i\sigma (i)}\\\langle 11\dots 1|{\hat {U}}|11\dots 1\rangle &={\rm {{Per(}\mathbf {\Lambda } {\rm {)}}}}\end{aligned}}$

where $S_{m}$ is the permutation group on $m$ elements. The second equality above follows from the fact that, upon expanding the product over $i$, the only terms in the sum that survive the inner product are those for which each ${\hat {a}}^{(j_{i})\dagger }$ appears exactly once. These are the permutations on the columns of $\mathbf {\Lambda }$. The third line follows from the second being simply the definition of the permanent.

Furthermore, we see that when $n<m$, and $s_{i}$, $t_{i}\in \{0,1\}$ for all $i\in {1,\dots ,m}$, $\mathbf {\Lambda } _{[s_{1},s_{2},\dots ,s_{m}][t_{1},t_{2},\dots ,t_{m}]}$, is a sub-matrix of $\mathbf {\Lambda }$. Any complex-valued matrix may be extended to a unitary by suitably padding and renormalizing such that the rows and columns form orthonormal bases. Thus, the amplitudes of linear optical quantum circuits correspond to the the permanents of general complex-valued matrices. Because an LOQC circuit can only sample from its corresponding probability distribution, what we actually have is an additive approximation scheme to the absolute values of permanents of these matrices.

Aaronson's Proof that the Permanent is #P-Hard

In 2011, Scott Aaronson gave a proof using a linear optical model of quantum computation that the permanent is #P-Hard. The proof relies on a reduction from the problem of counting solutions to a classically tractable Boolean function, which is #P-hard, to that of evaluating an LOQC circuit amplitude, which is the permanent of a complex-valued matrix.

The proof is as follows. Suppose we have a classical circuit $C$ that computes the Boolean function $C:\{0,1\}^{n}\rightarrow \{-1,1\}$, and let

$\Delta _{C}=\sum _{x\in \{0,1\}^{n}}C(x)$

then $\Delta _{C}$ is #P-hard. The circuit $Q=H_{2}^{\otimes n}D_{C}H_{2}^{\otimes n}$, where

${\begin{cases}{\begin{aligned}H_{2}^{\otimes n}|{\vec {0}}\rangle &={\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \\D_{C}|x\rangle &=C(x)|x\rangle \\\end{aligned}}\end{cases}}$

is such that $\langle {\vec {0}}|Q|{\vec {0}}\rangle ={\frac {\Delta _{C}}{2^{n}}}$. This circuit amplitude may be calculated using the postselection construction of Knill, Laflamme, and Milburn and is reducible to the permanent of a complex matrix, so all that remains is to show that, given $C$, the circuit description of $Q$ - or rather $D_{C}$ - can be produced in polynomial time. This is done using Charlie Bennett's "uncomputing trick"

$|x\rangle \rightarrow |x\rangle |h_{C}(x)\rangle \rightarrow C(x)|x\rangle |h_{C}(x)\rangle \rightarrow C(x)|x\rangle$

where $|h_{C}(x)\rangle$ is a state encoding the history of a computation of $C(x)$, which can be produced in polynomial time, as $C(x)$ is efficiently computable. In the first step, this state is generated on an ancilla register. In the next step, $C(x)$ is extracted as an overall phase via phase kick-back (by application of a $Z$-gate, for example). The computation that originally produced $h_{C}(x)$ is then performed in reverse, leading to the final state $C(x)|x\rangle$. This can be done coherently, and so a circuit description of of $Q$ may be efficiently produced given $C$. Therefore, given an oracle that efficiently computes the permanent of a complex-valued matrix, one may also compute the #P-hard problem $\Delta _{C}$.

Hierarchy Collapse

Aaronson also showed that if the output of a boson sampling model can be efficiently exactly sampled by a classical computer, then ${\rm {{P}^{\#{\rm {P}}}={\rm {{BPP}^{\rm {NP}}}}}}$, and thus the polynomial hierarchy collapses to the third level. Even if this could be done by a classical computer with an oracle for a polynomial hierarchy problem, then this would imply that ${\rm {{P}^{\#{\rm {P}}}\subseteq {\rm {{BPP}^{\rm {NP}}}}}}$, and so the polynomial hierarchy would still collapse by Toda's theorem. Because this collapse is believed to be unlikely, this is considered to be evidence that quantum computers can efficiently solve problems outside of the polynomial hierarchy. The proof relies on two facts, which Aaronson also proves:

1. Approximating the probability $p$ of some particular output configuration from a boson sampling model is #P-hard.
2. An exact polynomial-time algorithm for sampling from the output of a boson sampling model would imply a ${\rm {{BPP}^{\rm {NP}}}}$ algorithm for multiplicative approximation of $p$ via a technique called universal hashing.

Together, these imply that if sampling from the output of a boson sampling model is classically tractable, then ${\rm {{P}^{\#{\rm {P}}}={\rm {{BPP}^{\rm {NP}}}}}}$, and therefore the polynomial hierarchy collapses.