In 2010 Scott Aaronson and Alex Arkhipov posted a 95 page preprint on the quant-ph arxiv arguing that that linear optical interferometers cannot be efficiently simulated on classical computers. The argument is couched in quantum computational complexity theory, which can be daunting to those not skilled in that art.
Independently in 2011 our group was led to a similar conclusion in our attempts to predict the output of a specific linear optical interferometer we call the quantum pachinko machine. In light of the Arkhipov and Aaronson result we have gone back to investigate the complexity of this specific device and we have a new paper that explicitly constructs the Hilbert state space of the machine and shows that its dimension grows exponentially with all resources needed to build the device.
Our argument is only about 4 pages long and follows the logic of Feynman — If the Hilbert space is exponentially large then it is unlikely that a classical computer can simulate such a machine. We don't invoke any elements of quantum complexity theory in our argument, which may come as a relief to some physicists. The abstract of our new paper I present here:
Thus such linear optical interferometers, particularly with arbitrary Fock-state inputs, are likely not efficiently simulatable on a classical computer. The blow up in the Hilbert space is directly connected to the bosonic Fock states in the input. This comes as a bit of a surprise to us in the quantum optics community where the conventional wisdom had been that any linear optical device is always efficiently simulatable regardless of the input. To quote one of our co-authors, Hwang Lee, "This is shocking!"
Hence such linear optical interferometers, with their exponentially large Hilbert space, meet Feynman's necessary criterion for a universal quantum computer. Whether it is a universal quantum computer or not is an open question.
However, large-number photonic Fock states are highly susceptible to loss and dephasing, much more so than Gaussian states, and so whatever this thing is it is not a fault tolerant quantum computing machine. Error correction of some sort will need to be deployed to show that this is useful. Nevertheless, as Arkhipov and Aaronson note, linear optics with bosonic inputs is an interesting playground in quantum information processing.
We heartily agree with their assessment in our new paper.
Independently in 2011 our group was led to a similar conclusion in our attempts to predict the output of a specific linear optical interferometer we call the quantum pachinko machine. In light of the Arkhipov and Aaronson result we have gone back to investigate the complexity of this specific device and we have a new paper that explicitly constructs the Hilbert state space of the machine and shows that its dimension grows exponentially with all resources needed to build the device.
Our argument is only about 4 pages long and follows the logic of Feynman — If the Hilbert space is exponentially large then it is unlikely that a classical computer can simulate such a machine. We don't invoke any elements of quantum complexity theory in our argument, which may come as a relief to some physicists. The abstract of our new paper I present here:
"Aaronson and Arkhipov recently used computational complexity theory to argue that classical computers very likely cannot efficiently simulate linear, multimode, quantum-optical interferometers with arbitrary Fock-state inputs [S. Aaronson and A. Arkhipov, arXiv:1011.3245]. Here we present an elementary argument that utilizes only techniques from quantum optics. We explicitly construct the Hilbert space for such an interferometer and show that that its dimension scales exponentially with all the physical resources. Finally we also show that the Schrödinger and Heisenberg pictures of quantum theory, while mathematically equivalent, are not in general computationally equivalent."
Thus such linear optical interferometers, particularly with arbitrary Fock-state inputs, are likely not efficiently simulatable on a classical computer. The blow up in the Hilbert space is directly connected to the bosonic Fock states in the input. This comes as a bit of a surprise to us in the quantum optics community where the conventional wisdom had been that any linear optical device is always efficiently simulatable regardless of the input. To quote one of our co-authors, Hwang Lee, "This is shocking!"
Hence such linear optical interferometers, with their exponentially large Hilbert space, meet Feynman's necessary criterion for a universal quantum computer. Whether it is a universal quantum computer or not is an open question.
However, large-number photonic Fock states are highly susceptible to loss and dephasing, much more so than Gaussian states, and so whatever this thing is it is not a fault tolerant quantum computing machine. Error correction of some sort will need to be deployed to show that this is useful. Nevertheless, as Arkhipov and Aaronson note, linear optics with bosonic inputs is an interesting playground in quantum information processing.
We heartily agree with their assessment in our new paper.
