Continuous-time quantum walks (CTQWs) on dynamic graphs realize quantum gates as sequences of time-evolving graph Hamiltonians, but naive constructions produce long sequences with redundancy. Simplification rules, which are graph rewrite rules that shorten a dynamic graph sequence while preserving the unitary it implements, are the CTQW analogue of circuit identities in the gate model. In this work, we give CTQW realizations of the standard single-qubit gates and introduce new graph rewrite rules. We demonstrate the simplification rules through worked circuit reductions and outline their use as transpilation primitives for converting between the circuit model and the dynamic graph framework.
Continuous-time quantum walks (CTQWs) on dynamic graphs realize quantum gates as sequences of time-evolving graph Hamiltonians, but naive constructions produce long sequences with redundancy. Simplification rules, which are graph rewrite rules that shorten a dynamic graph sequence while preserving the unitary it implements, are the CTQW analogue of circuit identities in the gate model. In this work, we give CTQW realizations of the standard single-qubit gates and introduce new graph rewrite rules. We demonstrate the simplification rules through worked circuit reductions and outline their use as transpilation primitives for converting between the circuit model and the dynamic graph framework.
Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work we develop a mapping from dynamic CTQWs to the gate model of computation in the form of an algorithm to convert arbitrary single edge walks and single self loop walks, which are the fundamental building blocks of dynamic CTQWs, to their circuit model counterparts. We use this mapping to introduce an arbitrary quantum state preparation framework based on dynamic CTQWs. Our approach utilizes global information about the target state, relates state preparation to finding the optimal path in a graph, and leads to optimizations in the reduction of controls that are not as obvious in other approaches. Interestingly, classical optimization problems such as the minimal hitting set, minimum spanning tree, and shortest Hamiltonian path problems arise in our framework. We test our methods against uniformly controlled rotations methods, used by Qiskit, and find ours requires fewer CX gates when the target state has a polynomial number of non-zero amplitudes.
The continuous-time quantum walk is a quantum version of a random walk that evolves by Schrodinger's equation. With the Hamiltonian equal to the adjacency matrix of a sequence of graphs, called a dynamic graph, continuous-time quantum walks have been shown to implement quantum gates, including the T gate, Hadamard gate, and the Controlled{NOT gate. Since these gates make up a universal set of quantum gates, they can implement any other arbitrary quantum gate up to an arbitrary approximation. This process, however, can be tedious and ine cient. To alleviate this, we have developed a parameterized dynamic graph on which a continuous-time quantum walk can implement any arbitrary single-qubit quantum gate, and we have also extended this result to implement any two-qubit controlled-unitary quantum gate. These dynamic graphs have at most length three. Using these, we implemented Draper's quantum addition circuit, which is based on the quantum Fourier transform, using a continuous-time quantum walk on a dynamic graph.
It was recently shown that continuous-time quantum walks on dynamic graphs, i.e., sequences of static graphs whose edges change at specific times, can implement a universal set of quantum gates. This result treated all isolated vertices as having self-loops, so they all evolved by a phase under the quantum walk. In this paper, we permit isolated vertices to be loopless or looped, and loopless isolated vertices do not evolve at all under the quantum walk. Using this distinction, we construct simpler dynamic graphs that implement the Pauli gates and a set of universal quantum gates consisting of the Hadamard, T, and controlled-not gates, and these gates are easily extended to multiqubit systems. For example, the T gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of 4. We also construct a generalized phase gate, of which Z, S, and T are specific instances. Finally, we validate our implementations by numerically simulating a quantum circuit consisting of layers of one- and two-qubit gates, similar to those in recent quantum supremacy experiments, using a quantum walk.
In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. We develop a greedy matching heuristic and a compression-aware matching heuristic, both of which can be used in the quantum circuit algorithm. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare greedy (compression-aware) matching decomposition to a standard Pauli-based simulation pipeline and find that greedy (compression-aware) matching decomposition consistently yields substantial resource reductions, requiring up to 43% (70\%) fewer controlled gates and up to 54% (75\%) shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.
Continuous-time quantum walks (CTQWs) on static graphs provide efficient methods for search and sampling as well as a model for universal quantum computation. We consider an extension of CTQWs to the case of dynamic graphs, in which an ordered sequence of graphs governs free evolution of the quantum walk. We then consider how perfect state transfer during the quantum walk can be used to design dynamic graphs that implement a universal set of quantum logic gates. We give explicit examples for a complete logical basis, and we validate implementations using numerical simulations for quantum teleportation and addition circuits. Finally, we discuss the potential for realizing CTQWs on dynamic graphs using actively controlled quantum optical waveguides.
It is well known that any quantum gate can be decomposed into the universal gate set {T,H, cnot}, and recent results have shown that each of these gates can be implemented using a dynamic quantum walk, which is a continuous-time quantum walk on a sequence of graphs. This procedure for converting a quantum gate into a dynamic quantum walk, however, can result in long sequences of graphs. To alleviate this, in this paper, we develop a length-3 dynamic quantum walk that implements any single-qubit gate. Furthermore, we extend this result to give length-3 dynamic quantum walks that implement any single-qubit gate controlled by any number of qubits. Using these, we implement Draper's quantum addition circuit, which is based on the quantum Fourier transform, using a dynamic quantum walk.