Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the American Physical Society

Sampling complexity of interacting bosonic random walkers on a lattice

Gopikrishnan Muraleedharan, Sayonee Ray, Adrian Chapman, Akimasa Miyake, Ivan Deutsch

Published Mar 3, 2020• 0 citations
OpenAlex

Related papers

Boson sampling of multiple quantum random walkers on a lattice

Gopikrishnan Muraleedharan, Ivan Deutsch, Akimasa Miyake

Bulletin of the American Physical Society•Mar 7, 2018•0 citations

Boson sampling of many-body quantum random walkers on a lattice

Gopikrishnan Muraleedharan, Akimasa Miyake, Ivan Deutsch

Bulletin of the American Physical Society•Mar 14, 2017•0 citations

Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice

Gopikrishnan Muraleedharan, Akimasa Miyake, Ivan Deutsch

Abstract We study the sampling complexity of a probability distribution associated with an ensemble of identical noninteracting bosons undergoing a quantum random walk on a one-dimensional lattice. With uniform nearest-neighbor hopping we show that one can efficiently sample the distribution for times logarithmic in the size of the system, while for longer times there is no known efficient sampling algorithm. With time-dependent hopping and optimal control, we design the time evolution to approximate an arbitrary Haar-random unitary map analogous to that designed for photons in a linear optical network. This approach highlights a route to generating quantum complexity by optimal control only of a single-body unitary matrix. We study this in the context of two potential experimental realizations: a spinor optical lattice of ultracold atoms and a quantum gas microscope.

arXiv:1805.01858•New Journal of Physics•Feb 11, 2019•27 citations

The Quantum Complexity of Markov Chain Monte Carlo

Peter C. Richter

Springer eBooks•Jun 10, 2008•0 citations

Homogeneous Open Quantum Random Walks on a Lattice

Raffaella Carbone, Yan Pautrat

arXiv:1408.1113•Journal of Statistical Physics•May 25, 2015•41 citations

Sampling complexity of Bosonic random walkers on a one-dimensional lattice

Gopikrishnan Muraleedharan, Akimasa Miyake, Ivan Deutsch

Computers based quantum logic are believed to solve problems faster and more efficiently than computers based on classical boolean logic. However, a large-scale universal quantum computer with error correction may not be realized in near future. But we can ask the question: can we devise a specific problem that a quantum device can solve faster than current state of the art super computers? One such problem is the so called "Boson Sampling" problem introduced by Aaronson and Arkhipov. The problem is to generate random numbers according to same distribution as the output number configurations of photons in linear optics. It was shown that this is a very hard task for classical computers, but can be realized using quantum devices. However, realizing this in photonic systems is proving to be harder than ever because of various challenges in preparation and measurements. We propose and analyze an alternate platform to implement this problem, ultra-cold atoms trapped in one-dimensional optical lattices.

•Jan 1, 2018•0 citations
Abstract We study the sampling complexity of a probability distribution associated with an ensemble of identical noninteracting bosons undergoing a quantum random walk on a one-dimensional lattice. With uniform nearest-neighbor hopping we show that one can efficiently sample the distribution for times logarithmic in the size of the system, while for longer times there is no known efficient sampling algorithm. With time-dependent hopping and optimal control, we design the time evolution to approximate an arbitrary Haar-random unitary map analogous to that designed for photons in a linear optical network. This approach highlights a route to generating quantum complexity by optimal control only of a single-body unitary matrix. We study this in the context of two potential experimental realizations: a spinor optical lattice of ultracold atoms and a quantum gas microscope.
Computers based quantum logic are believed to solve problems faster and more efficiently than computers based on classical boolean logic. However, a large-scale universal quantum computer with error correction may not be realized in near future. But we can ask the question: can we devise a specific problem that a quantum device can solve faster than current state of the art super computers? One such problem is the so called "Boson Sampling" problem introduced by Aaronson and Arkhipov. The problem is to generate random numbers according to same distribution as the output number configurations of photons in linear optics. It was shown that this is a very hard task for classical computers, but can be realized using quantum devices. However, realizing this in photonic systems is proving to be harder than ever because of various challenges in preparation and measurements. We propose and analyze an alternate platform to implement this problem, ultra-cold atoms trapped in one-dimensional optical lattices.