Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
arXiv:1805.01858 · doi:10.1088/1367-2630/ab0610
Abstract
We study the sampling complexity of a probability distribution associated with an ensemble ofidentical 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 fortimes logarithmic in the size of the system, while for longer times there is no known efficient samplingalgorithm. With time-dependent hopping and optimal control, we design the time evolution toapproximate an arbitrary Haar-random unitary map analogous to that designed for photons in alinear optical network. This approach highlights a route to generating quantum complexity byoptimal control only of a single-body unitary matrix. We study this in the context of two potentialexperimental realizations: a spinor optical lattice of ultracold atoms and a quantum gas microscope.
arXiv comment10+3 pages, 6 figures: Published version
References in corpus (68)
- Efficient classical simulation of slightly entangled quantum computations
- Observation of many-body localization of interacting fermions in a quasi-random optical lattice
- A quantum gas microscope - detecting single atoms in a Hubbard regime optical lattice
- Single-Atom Resolved Fluorescence Imaging of an Atomic Mott Insulator
- Quantum Computation and Decision Trees
- Characterizing Quantum Supremacy in Near-Term Devices
- Measuring entanglement entropy through the interference of quantum many-body twins
- Quantum thermalization through entanglement in an isolated many-body system
- Control of quantum phenomena: Past, present, and future
- Boson Sampling on a Photonic Chip
- Quantum Computational Supremacy
- Quantum entanglement in condensed matter systems
- Experimental Boson Sampling
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
- Optimal Control at the Quantum Speed Limit
- Coherent transport of neutral atoms in spin-dependent optical lattice potentials
- Universal computation by multi-particle quantum walk
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Strongly Correlated Quantum Walks in Optical Lattices
- Random Quantum Circuits are Approximate 2-designs
- Local random quantum circuits are approximate polynomial-designs
- Boson Sampling from Gaussian States
- Quantum random walks in optical lattices
- Cooling a single atom in an optical tweezer to its quantum ground state
- Quantum-state control in optical lattices
- Hong-Ou-Mandel atom interferometry in tunnel-coupled optical tweezers
- Alkaline earth atoms in optical tweezers
- Microscopic control and detection of ultracold strontium in optical-tweezer arrays
- BosonSampling with single-photon Fock states from a bright solid-state source
- No imminent quantum supremacy by boson sampling
- Scalable boson sampling with a single-photon device
- Electric quantum walks with individual atoms
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Stringent and efficient assessment of Boson-Sampling devices
- Efficient Generation of Generic Entanglement
- Generalized multi-photon quantum interference
- Quantum Walk of Two Interacting Bosons
- Convergence rates for arbitrary statistical moments of random quantum circuits
- What can quantum optics say about computational complexity theory?
- Quantum process tomography of unitary and near-unitary maps
- Degrees of controllability for quantum systems and applications to atomic systems
- Exploring constrained quantum control landscapes
- Exact convergence times for generation of random bipartite entanglement
- BosonSampling with Lost Photons
- Microwave Control of Atomic Motion in Optical Lattices
- Spectroscopic determination of the s-wave scattering lengths of 86Sr and 88Sr
- Driven quantum dynamics: will it blend?
- Statistics-dependent quantum co-walking of two particles in one-dimensional lattices with nearest-neighbor interactions
- Microwave control of atomic motional states in a spin-dependent optical lattice
- Dynamical phase transitions in sampling complexity
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
- Totally Destructive Many-Particle Interference
- Unitary -designs from random - and -diagonal unitaries
- Measurement-based entanglement of noninteracting bosonic atoms
- Fast dynamics for atoms in optical lattices
- Driven Boson Sampling
- The Hong-Ou-Mandel effect with atoms
- An introduction to boson-sampling
- An efficient tree decomposition method for permanents and mixed discriminants
- Bose-Hubbard model for universal quantum walk-based computation
- The scaling of boson sampling experiments
- Coherent control of atomic transport in spinor optical lattices
- Direct Observation and Analysis of Spin Dependent Transport of Single Atoms in a 1D Optical Lattice
- Quantum Walks With Neutral Atoms: Quantum Interference Effects of One and Two Particles
Cited by in corpus (21)
- Efficient classical simulation of random shallow 2D quantum circuits
- Computational advantage of quantum random sampling
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Hierarchy of linear light cones with long-range interactions
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Temporal Entanglement in Chaotic Quantum Circuits
- An atomic boson sampler
- Finite speed of quantum information in models of interacting bosons at finite density
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians
- Page curves and typical entanglement in linear optics
- Quantum walks with quantum chaotic coins: Of the Loschmidt echo, classical limit and thermalization
- Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
- Excited-Band Coherent Delocalization for Improved Optical Lattice Clock Performance
- Out-of-time-ordered correlators and quantum walks
- Inhibition of spread of typical bipartite and genuine multiparty entanglement in response to disorder
- Quantum advantage from energy measurements of many-body quantum systems
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Demonstration of Discrete-Time Quantum Walks and Observation of Topological Edge States in a Superconducting Qutrit Chain
- Boson sampling with ultracold atoms in a programmable optical lattice
- Dynamical complexity of non-Gaussian many-body systems with dissipation
- Protocol for autonomous rearrangement of cold atoms into low-entropy configurations