Simulation of quantum random walks using linear optical devices

慎太郎 田家, 靖司 素川, 歴舟 山崎

Changhun Oh, Youngrong Lim, Bill Fefferman +1 more

Sampling from probability distributions of quantum circuits is a fundamentally and practically important task which can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In the present work, we examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits composed of random beam splitters with equally distributed squeezed vacuum states and single-photon states input. We provide efficient classical algorithms to simulate linear-optical random circuits and show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources using a classical random walk behavior of random linear-optical circuits. Notably, the average-case depth allowing an efficient classical simulation is larger than the worst-case depth limit, which is linear in the distance. Besides, our results together with the hardness of boson sampling give a lower-bound on the depth for constituting global Haar-random unitary circuits.

Shuto Osawa, David S. Simon, Alexander V. Sergienko

All existing optical quantum walk approaches are based on the use of beamsplitters and multiple paths to explore the multitude of unitary transformations of quantum amplitudes in a Hilbert space. The beamsplitter is naturally a directionally biased device: the photon cannot travel in the reverse direction. This causes rapid increases in the optical hardware resources required for complex quantum walk applications, since the number of options for the walking particle grows with each step. Here we present the experimental demonstration of a directionally-unbiased linear-optical multiport, which allows reversibility of the photon direction. An amplitude-controllable probability distribution matrix for a unitary three-edge vertex is reconstructed with only linear-optical devices. Such directionally-unbiased multiports allow direct execution of quantum walks over a multitude of complex graphs and in tensor networks. This approach would enable simulation of complex Hamiltonians of physical systems and quantum walk applications in a more efficient and compact setup, substantially reducing the required hardware resources.

Uğur Küçük, A. C. Cem Say

Zbigniew Haba

Zhi Zhao, Jiangfeng Du, Hui Li +3 more

The quantum random walk has drawn special interests because its remarkable features to the classical counterpart could lead to new quantum algorithms. In this paper, we propose a feasible scheme to implement quantum random walks on a line using only linear optics elements. With current single-photon interference technology, the steps that could be experimentally implemented can be extended to very large numbers. We also show that, by decohering the quantum states, our scheme for quantum random walk tends to be classical.