Quantum circuits for simulating linear interferometers

Motivated by recent proposals for quantum proof of work protocols, we investigate approaches for simulating linear optical interferometers using digital quantum circuits. We focus on a second quantization approach, where the quantum computer's registers represent optical modes. We can then use standard quantum optical techniques to decompose the unitary matrix describing an interferometer into an array of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mrow> <a:mn>2</a:mn> <a:mo>×</a:mo> <a:mn>2</a:mn> </a:mrow> </a:math> unitaries, which are subsequently synthesized into quantum circuits and stitched together to complete the circuit. For an <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mi>m</b:mi> </b:math> -mode interferometer with <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mi>n</c:mi> </c:math> identical photons, this method requires approximately <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"> <d:mrow> <d:mi mathvariant="script">O</d:mi> <d:mo>(</d:mo> <d:mi>m</d:mi> <d:mo form="prefix">log</d:mo> <d:mo>(</d:mo> <d:mi>n</d:mi> <d:mo>)</d:mo> <d:mo>)</d:mo> </d:mrow> </d:math> qubits and a circuit depth of <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"> <g:mrow> <g:mi mathvariant="script">O</g:mi> <g:mo>(</g:mo> <g:mi>m</g:mi> <g:msup> <g:mi>n</g:mi> <g:mn>4</g:mn> </g:msup> <g:msub> <g:mo form="prefix">log</g:mo> <g:mn>2</g:mn> </g:msub> <g:mrow> <g:mo>(</g:mo> <g:mi>n</g:mi> <g:mo>)</g:mo> </g:mrow> <g:mspace width="0.222222em"/> <g:mtext>polylog</g:mtext> <g:mrow> <g:mo>(</g:mo> <g:msup> <g:mi>n</g:mi> <g:mn>4</g:mn> </g:msup> <g:mo>/</g:mo> <g:mi>ε</g:mi> <g:mo>)</g:mo> </g:mrow> <g:mo>)</g:mo> </g:mrow> </g:math> . We present a software package aquinas (a quantum interferometer assembler) that uses this approach to generate such quantum circuits. For reference, an arbitrary five-mode interferometer with two identical photons is compiled to a ten-qubit quantum circuit with a depth of 1972.