Related papers: Discrete Quantum Walks on the Symmetric Group

Discrete Quantum Walks on the Symmetric Group

URL: http://arxiv.org/abs/2203.15148v2
Date: Mon, 9 May 2022 00:07:22 GMT
Title: Discrete Quantum Walks on the Symmetric Group
Authors: Avah Banerjee
Abstract summary: In quantum walks, the propagation is governed by quantum mechanical rules; generalizing random walks to the quantum setting. In this paper we investigate the discrete time coined quantum walk (DTCQW) model using tools from non-commutative Fourier analysis. Specifically, we are interested in characterizing the DTCQW on Cayley graphs generated by the symmetric group ($sym$) with appropriate generating sets.
Score: 0.0
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: The theory of random walks on finite graphs is well developed with numerous applications. In quantum walks, the propagation is governed by quantum mechanical rules; generalizing random walks to the quantum setting. They have been successfully applied in the development of quantum algorithms. In particular, to solve problems that can be mapped to searching or property testing on some specific graph. In this paper we investigate the discrete time coined quantum walk (DTCQW) model using tools from non-commutative Fourier analysis. Specifically, we are interested in characterizing the DTCQW on Cayley graphs generated by the symmetric group ($\sym$) with appropriate generating sets. The lack of commutativity makes it challenging to find an analytical description of the limiting behavior with respect to the spectrum of the walk-operator. We determine certain characteristics of these walks using a path integral approach over the characters of $\sym$.

Related papers

Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
arXiv Detail & Related papers (2024-08-19T09:15:54Z)
Quantum walks, the discrete wave equation and Chebyshev polynomials [1.0878040851638]
A quantum walk is the quantum analogue of a random walk. We show that quantum walks can speed up the spreading or mixing rate of random walks on graphs.
arXiv Detail & Related papers (2024-02-12T17:15:19Z)
Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. This work has potential applications in algorithms for sampling non-abelian groups, graph isomorphism tests, etc.
arXiv Detail & Related papers (2023-12-25T11:21:55Z)
Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
arXiv Detail & Related papers (2021-12-23T17:57:49Z)
Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z)
How to Teach a Quantum Computer a Probability Distribution [0.0]
We explore teaching a coined discrete time quantum walk on a regular graph a probability distribution. We also discuss some hardware and software concerns as well as immediate applications and the several connections to machine learning.
arXiv Detail & Related papers (2021-04-15T02:41:27Z)
Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z)
Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
arXiv Detail & Related papers (2020-05-13T14:53:36Z)
Discrete-Time Quantum Walks on Oriented Graphs [0.0]
We define discrete-time quantum walks on arbitrary oriented graphs. We introduce a parameter, called alpha, that quantifies the amount of orientation.
arXiv Detail & Related papers (2020-01-13T01:42:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.