We show that with the addition of multiple walkers, quantum walks on a line can be transformed into lattice graphs of higher dimension. Thus, multi-walker walks can simulate single-walker walks on higher dimensional graphs and vice versa. This exponential complexity opens up new applications for present-day quantum walk experiments. We discuss the applications of such higher-dimensional structures and how they relate to linear optics quantum computing. In particular we show that multi-walker quantum walks are equivalent to the BosonSampling model for linear optics quantum computation proposed by Aaronson & Arkhipov. With the addition of control over phase-defects in the lattice, which can be simulated with entangling gates, asymmetric lattice structures can be constructed which are universal for quantum computation.
We show that with the addition of multiple walkers, quantum walks on a line can be transformed into lattice graphs of higher dimension. Thus, multi-walker walks can simulate single-walker walks on higher dimensional graphs and vice versa. This exponential complexity opens up new applications for present-day quantum walk experiments. We discuss the applications of such higher-dimensional structures and how they relate to linear optics quantum computing. In particular we show that multi-walker quantum walks are equivalent to the BosonSampling model for linear optics quantum computation proposed by Aaronson & Arkhipov. With the addition of control over phase-defects in the lattice, which can be simulated with entangling gates, asymmetric lattice structures can be constructed which are universal for quantum computation.
We show that with the addition of multiple walkers, quantum walks on a line can be transformed into lattice graphs of higher dimension. Thus, multi-walker walks can simulate single-walker walks on higher dimensional graphs and vice versa. This exponential complexity opens up new applications for present-day quantum walk experiments. We discuss the applications of such higher-dimensional structures and how they relate to linear optics quantum computing. In particular we show that multi-walker quantum walks are equivalent to the BosonSampling model for linear optics quantum computation proposed by Aaronson & Arkhipov. With the addition of control over phase-defects in the lattice, which can be simulated with entangling gates, asymmetric lattice structures can be constructed which are universal for quantum computation.
Quantum walks have emerged as an interesting alternative to the usual circuit model for quantum computing. While still universal for quantum computing, the quantum walk model has very different physical requirements, which lends itself more naturally to some physical implementations, such as linear optics. Numerous authors have considered walks with one or two walkers, on one dimensional graphs, and several experimental demonstrations have been performed. In this paper we discuss generalizing the model of discrete time quantum walks to the case of an arbitrary number of walkers acting on arbitrary graph structures. We present a formalism which allows for analysis of such situations, and several example scenarios for how our techniques can be applied. We consider the most important features of quantum walks -- measurement, distinguishability, characterization, and the distinction between classical and quantum interference. We also discuss the potential for physical implementation in the context of linear optics, which is of relevance to present day experiments.
Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.
Abstract Quantum Walks are unitary processes describing the evolution of an initially localized wavefunction on a lattice potential. The complexity of the dynamics increases significantly when several indistinguishable quantum walkers propagate on the same lattice simultaneously, as these develop non-trivial spatial correlations that depend on the particle’s quantum statistics, mutual interactions, initial positions, and the lattice potential. We show that even in the simplest case of a quantum walk on a one dimensional graph, these correlations can be shaped to yield a complete set of compact quantum logic operations. We provide detailed recipes for implementing quantum logic on one-dimensional quantum walks in two general cases. For non-interacting bosons—such as photons in waveguide lattices—we find high-fidelity probabilistic quantum gates that could be integrated into linear optics quantum computation schemes. For interacting quantum-walkers on a one-dimensional lattice—a situation that has recently been demonstrated using ultra-cold atoms—we find deterministic logic operations that are universal for quantum information processing. The suggested implementation requires minimal resources and a level of control that is within reach using recently demonstrated techniques. Further work is required to address error-correction.
Quantum walks in an elaborately designed graph, is a powerful tool simulating physical and topological phenomena, constructing analog quantum algorithms and realizing universal quantum computing. Integrated photonics technology has emerged as a versatile platform to implement various quantum information tasks and a promising candidate to perform large-scale quantum walks. Both extending physical dimensions and involving more particles will increase the complexity of the evolving systems and the desired quantum resources. Pioneer works have demonstrated single particle walking on two-dimensional (2D) lattices and multiple walkers interfering on a one-dimensional structure. However, 2D multi-particle quantum walk, genuinely being not classically simulatable, has been a vacancy for nearly ten years. Here, we present a genuine 2D quantum walk with correlated photons on a triangular photonic lattice, which can be mapped to a state space up to 37X37 dimensions. This breaks through the physically restriction of single-particle evolution, which can encode information in a large space and constitute high-dimensional graphs indeed beneficial to quantum information processing. A site-by-site addressing between the chip facet and the 2D fanout interface enables an observation of over 600 non-classical interferences simultaneously, violating a classical limit up to 57 standard deviations. Our platform offers a promising prospect for multi-photon quantum walks in a large-scale 2D arrangement, paving the way for practical quantum simulation and quantum computation beyond classical regime.
Quantum walks in an elaborately designed graph are a powerful tool for simulating physical and topological phenomena, constructing novel quantum algorithms, and realizing universal quantum computing. Integrated photonics technology has emerged as a versatile platform for implementing a variety of quantum information tasks and as a promising candidate for performing large-scale quantum walks. Both extending physical dimensions and involving more particles will increase the complexity of the evolving systems. Pioneering studies have demonstrated a single particle walking on two-dimensional lattices and multiple walkers interfering on a one-dimensional structure. However, multiple particles evolving in a genuine two-dimensional space in a scalable fashion has remained a vacancy for nearly 10 years. We present a genuine two-dimensional quantum walk with correlated photons on a triangular photonic lattice, which is mapped to a 37 × 37 high-dimensional state space. The genuine two-dimensional quantum walk breaks through the physical restrictions of single-particle evolution, allowing for the encoding of information in large spaces and construction of high-dimensional graphs, which are beneficial for quantum information processing. Between the chip and the two-dimensional fanout interface, site-by-site addressing enables simultaneous detection of over 600 nonclassical interferences and observation of quantum correlations that violate a classical limit by 57 standard deviations. Our implementation provides a paradigm for multi-photon quantum walks in a two-dimensional configuration on a large scale, paving the way for practical quantum simulation and computation beyond the classical regime.