Efficient quantum circuits for continuous-time quantum walks on composite graphs

Abstract

In this paper, we investigate the simulation of continuous-time quantum walks on specific classes of graphs, for which it is possible to fast-forward the time-evolution operator to achieve constant-time simulation complexity and to perform the simulation exactly, while maintaining $\mbox{poly}(\mbox{log}(n))$ efficiency. In particular, we discuss two classes of composite graphs, commuting graphs and Cartesian product of graphs, that contain classes of graphs which can be simulated in this fashion. This allows us to identify new families of graphs that we can efficiently simulate in a quantum circuit framework, providing practical and explicit means to explore quantum-walk based algorithms in laboratories.

References in corpus (21)

• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Universal computation by quantum walk
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Universal computation by multi-particle quantum walk
• An example of the difference between quantum and classical random walks
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Search via Quantum Walk
• Two-particle quantum walks applied to the graph isomorphism problem
• Google in a Quantum Network
• Classical approach to the graph isomorphism problem using quantum walks
• Efficient Quantum Walk on a Quantum Processor
• Quantum Google in a Complex Network
• Simulating Quantum Dynamics On A Quantum Computer
• Simulating sparse Hamiltonians with star decompositions
• Efficient quantum circuits for arbitrary sparse unitaries
• Qcompiler: quantum compilation with CSD method

Cited by in corpus (11)

• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Quantum walk-based portfolio optimisation
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Link prediction with continuous-time classical and quantum walks
• Deterministic spatial search using alternating quantum walks
• Efficient implementation of discrete-time quantum walks on quantum computers
• A framework for optimal quantum spatial search using alternating phase-walks
• Implementation of Continuous-Time Quantum Walk on Sparse Graph
• Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation
• Quantum spatial search with electric potential : long-time dynamics and robustness to noise
• Implementation of Continuous-Time Quantum Walks on Quantum Computers