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

DOI10.1088/1751-8121/AA53A9MaRDI QIDQ2965745zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(4)

• A method for exact simulation of quantum dynamics
• Unitary coined discrete-time quantum walks on directed multigraphs
• Simplifying continuous-time quantum walks on dynamic graphs
• Efficient discrete-time simulations of continuous-time quantum query algorithms

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)