Experimental Quantum Fast Hitting on Hexagonal Graphs
arXiv:1807.06625 · doi:10.1038/s41566-018-0282-5
Abstract
Quantum walks are powerful kernels in quantum computing protocols that possess strong capabilities in speeding up various simulation and optimisation tasks. One striking example is given by quantum walkers evolving on glued trees for their faster hitting performances than in the case of classical random walks. However, its experimental implementation is challenging as it involves highly complex arrangements of exponentially increasing number of nodes. Here we propose an alternative structure with a polynomially increasing number of nodes. We successfully map such graphs on quantum photonic chips using femtosecond laser direct writing techniques in a geometrically scalable fashion. We experimentally demonstrate quantum fast hitting by implementing two-dimensional quantum walks on these graphs with up to 160 nodes and a depth of 8 layers, achieving a linear relationship between the optimal hitting time and the network depth. Our results open up a scalable way towards quantum speed-up in complex problems classically intractable.
16 pages, 12 figures
References in corpus (29)
- Quantum Computation and Decision Trees
- Quantum walks of correlated particles
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Experimental boson sampling in arbitrary integrated photonic circuits
- Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Quantum walk of a trapped ion in phase space
- An example of the difference between quantum and classical random walks
- Strongly Correlated Quantum Walks in Optical Lattices
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Discrete single-photon quantum walks with tunable decoherence
- Quantum algorithms for algebraic problems
- Experimental Implementation of the Quantum Random-Walk Algorithm
- Experimental Two-dimensional Quantum Walk on a Photonic Chip
- Photonic quantum walk in a single beam with twisted light
- Quantum walks and wavepacket dynamics on a lattice with twisted photons
- Entanglement in coined quantum walks on regular graphs
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Quantum Navigation and Ranking in Complex Networks
- Classical approach to the graph isomorphism problem using quantum walks
- Tuneable quantum interference in a 3D integrated circuit
- Experimental realisation of a delayed-choice quantum walk
- Quantum interference with beamlike type-II spontaneous parametric down-conversion
- Transport properties of continuous-time quantum walks on Sierpinski fractals
- Non-classical photon correlation in a two-dimensional photonic lattice
- Invisibility Cloak Printed on a Photonic Chip
- Decoherence enhances performance of quantum walks applied to graph isomorphism testing
- Mapping and Measuring Large-scale Photonic Correlation with Single-photon Imaging
Cited by in corpus (32)
- Integrated Photonic Quantum Technologies
- Femtosecond laser micromachining for integrated quantum photonics
- Direct Observation of Topology from Single-photon Dynamics on a Photonic Chip
- Two-dimensional topological quantum walks in the momentum space of structured light
- A synthetic gauge field for two-dimensional time-multiplexed quantum random walks
- A Scalable Photonic Computer Solving the Subset Sum Problem
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Combinatorial optimisation via highly efficient quantum walks
- Ultra-long quantum walks via spin-orbit photonics
- Experimental quantum stochastic walks simulating associative memory of Hopfield neural networks
- Generating Haar-uniform Randomness using Stochastic Quantum Walks on a Photonic Chip
- Quantum spatial search in two-dimensional waveguide arrays
- Information processing at the speed of light
- Continuous-time quantum walks on planar lattices and the role of the magnetic field
- Engineering topological states and quantum-inspired information processing using classical circuits
- Implementation of a 3 x 3 directionally-unbiased linear optical multiport
- Simulating Photosynthetic Energy Transport on a Photonic Network
- Quantum verification of NP problems with single photons and linear optics
- Photonic Newton's Cradle for Remote Energy Transport
- Timestamp Boson Sampling
- Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
- Quantum Slide and NAND Tree on a Photonic Chip
- Resonances of recurrence time of monitored quantum walks
- Observing Movement of Dirac Cones from Single-Photon Dynamics
- Experimental Quantum Simulation of Dynamic Localization on Curved Photonic Lattices
- Generation of True Quantum Random Numbers with On-Demand Probability Distributions via Single-Photon Quantum Walks
- Second-order topological insulator in a coinless discrete-time quantum walk
- Quantum walk state transfer on a hypercube
- Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
- Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
- Impact of Bivariate Gaussian Potentials on Quantum Walks for Spatial Search
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice