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

DOI10.1088/1751-8121/AA53A9zbMATH Open1359.81085arXiv1610.07107OpenAlexW3103749232MaRDI QIDQ2965745FDOQ2965745

Authors: T. Loke, Jingbo B. Wang 

Publication date: 3 March 2017

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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 $mboxpoly(mboxlog(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.

Full work available at URL: https://arxiv.org/abs/1610.07107

Recommendations

• Simplifying continuous-time quantum walks on dynamic graphs
• On the relationship between continuous- and discrete-time quantum walk
• Efficient circuits for quantum walks
• QUANTUM WALKS ON GENERAL GRAPHS
• Exact simulation of coined quantum walks with the continuous-time model

zbMATH Keywords

quantum circuitquantum walkcomposite graph

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Random walks on graphs (05C81) Applications of graph theory to circuits and networks (94C15)

Cites Work

• Title not available (Why is that?)
• Search via Quantum Walk
• Universal Quantum Simulators
• Adiabatic quantum state generation and statistical zero knowledge
• Exponential algorithmic speedup by a quantum walk
• On the relationship between continuous- and discrete-time quantum walk
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Physical implementation of quantum walks
• A survey of the theory of hypercube graphs
• An example of the difference between quantum and classical random walks
• A classical approach to the graph isomorphism problem using quantum walks
• Universal Computation by Multiparticle Quantum Walk
• Simulating Sparse Hamiltonians with Star Decompositions
• On mixing in continuous-time quantum walks on some circulant graphs
• \(Qcompiler\): quantum compilation with the CSD method
• \textit{OptQC}: an optimized parallel quantum compiler
• Exact analytical results for quantum walks on star graphs
• Black-box Hamiltonian simulation and unitary implementation
• Simulating quantum dynamics on a quantum computer
• Limitations on the simulation of non-sparse Hamiltonians
• Efficient circuits for quantum walks

Cited In (2)

• A method for exact simulation of quantum dynamics
• Unitary coined discrete-time quantum walks on directed multigraphs

This page was built for publication: Efficient quantum circuits for continuous-time quantum walks on composite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965745)