Efficient and scalable quantum walk algorithms via the quantum Fourier transform
- PDF / 1,357,780 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 18 Downloads / 201 Views
Efficient and scalable quantum walk algorithms via the quantum Fourier transform Asif Shakeel1 Received: 8 May 2020 / Accepted: 18 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Quantum walks (QWs) are of interest as examples of uniquely quantum behavior and are applicable in a variety of quantum search and simulation models. Implementing QWs on quantum devices is useful from both points of view. Taking advantage of the symmetry inherent in the QW description, we decompose the matrix description of the one-dimensional discrete time QW algorithm. This yields a highly efficient and scalable, quadratic size, linear depth circuit for the basic discrete-time QW that utilizes quantum Fourier transform (QFT) to implement the shift. QFT further allows us to generalize the shift of the basic QW to unitary spatial convolutions. On Noisy Intermediate-Scale Quantum (NISQ) devices, in which fewer computations imply faster execution and reduced effects of noise and decoherence, this scheme is especially relevant. As a demonstration, we simulate our basic QW algorithm on publicly accessible IBM quantum computers. Keywords Quantum walks · Quantum algorithms · Quantum simulation · Efficient algorithm
1 Introduction Quantum walks (QWs) exhibit properties that are fundamentally quantum mechanical, serving to demonstrate in their most basic form, walk patterns that are unachievable by classical random walks. In their sophisticated configurations, they appear in applications in areas as widely apart as quantum simulation models [1,2] and quantum search algorithms [3]. QWs have been experimentally realized on different physical systems [4,5]. The reader is referred to [6] for a comprehensive review of QWs. With the public availability of quantum computers, quantum algorithms can be tested and their resource requirements and performance examined. In the current era of Noisy
B 1
Asif Shakeel [email protected] San Diego, CA 95120, USA 0123456789().: V,-vol
123
323
Page 2 of 26
A. Shakeel
Intermediate-Scale Quantum (NISQ) [7] devices, decoherence and noise may severely degrade the performance of a quantum algorithm implemented on a device, negating any gains to be had from a using a quantum algorithm over a classical one. As a consequence, the issue of resource use in implementation deserves consideration. In this paper, we develop a computational description of a one-dimensional discrete-time QW that turns into a flexible, scalable and highly efficient implementation in terms of circuit size and depth.1 It also illustrates that partial optimization of an algorithm can be done mathematically prior to circuit implementation on a quantum device. A discrete-time QW is specified by a particle walking on a lattice, at each time step moving from its current position or site to another in its vicinity, and scattering through self-interaction. We will, for this paper, consider a one-dimensional walk on a finite lattice. The state of the QW is specified by its position and velocity. Taking th
Data Loading...
