Search for a command to run...
In a boson sampling quantum optical experiment, we send <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mi>n</a:mi> </a:math> individual photons into an <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mi>m</b:mi> </b:math> -mode interferometer and measure the occupation pattern on the output. The statistics of this process depend on the permanent of a matrix representing the experiment, which is itself a #P-hard problem to compute, and this is the reason why ideal and fully general boson sampling is hard to simulate on a classical computer. We exploit the fact that, for a nearest-neighbor shallow circuit, i.e., depth <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mrow> <c:mi>D</c:mi> <c:mo>=</c:mo> <c:mtext>O</c:mtext> <c:mo>(</c:mo> <c:mo form="prefix">log</c:mo> <c:mi>m</c:mi> <c:mo>)</c:mo> </c:mrow> </c:math> , one can adapt the algorithm by Clifford and Clifford [SODA '18 (2018), pp. 146–155] to exploit the sparsity of the shallow interferometer using an algorithm by Cifuentes and Parrilo [] that can efficiently compute a permanent of a structured matrix from a tree decomposition. Our algorithm generates a sample from a shallow circuit in time <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"> <e:mrow> <e:mtext>O</e:mtext> <e:mrow> <e:mo>(</e:mo> <e:msup> <e:mi>n</e:mi> <e:mn>2</e:mn> </e:msup> <e:msup> <e:mn>2</e:mn> <e:mi>ω</e:mi> </e:msup> <e:msup> <e:mi>ω</e:mi> <e:mn>2</e:mn> </e:msup> <e:mo>)</e:mo> </e:mrow> <e:mo>+</e:mo> <e:mtext>O</e:mtext> <e:mrow> <e:mo>(</e:mo> <e:mi>ω</e:mi> <e:msup> <e:mi>n</e:mi> <e:mn>3</e:mn> </e:msup> <e:mo>)</e:mo> </e:mrow> </e:mrow> </e:math> , where <f:math xmlns:f="http://www.w3.org/1998/Math/MathML"> <f:mi>ω</f:mi> </f:math> is the treewidth of the decomposition that satisfies <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"> <g:mrow> <g:mi>ω</g:mi> <g:mo>≤</g:mo> <g:mn>2</g:mn> <g:mi>D</g:mi> </g:mrow> </g:math> for nearest-neighbor shallow circuits. The key difference in our work with respect to previous work using similar methods is the reuse of the structure of the tree decomposition, allowing us to adapt the Laplace expansion used by Clifford and Clifford, which removes a significant factor of <h:math xmlns:h="http://www.w3.org/1998/Math/MathML"> <h:mi>m</h:mi> </h:math> from the running time, especially as <i:math xmlns:i="http://www.w3.org/1998/Math/MathML"> <i:mrow> <i:mi>m</i:mi> <i:mo>></i:mo> <i:msup> <i:mi>n</i:mi> <i:mn>2</i:mn> </i:msup> </i:mrow> </i:math> is a requirement of the original boson sampling proposal.