This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.
This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.
This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.
Quantum walks have been extensively studied recently, mainly due to their
vast difference in behavior to classical random walks. This paper is concerned
with discrete time and space quantum walks of particles that propagate through
a one-dimensional line. This line can be either a lattice or a graph or any
other form of mathematical structure that can be viewed as a one-dimensional
line. First is defined a concrete way to describe the unitary evolution of a
quantum walk through a balanced coin operator and a shift operator. Then
follows the implementation of the quantum walk on an 8-cycle, i.e a cycle
graph with 8 nodes, which is then run locally as a simulation and on IBM's
quantum computer. The paper explores two implementations of the quantum walk as
a quantum circuit: the first one consists of generalised controlled inversions,
as introduced in \cite{EffWalk}, whereas the second one tries to replace them
with rotation operators around the basis states. The main aim is to find a way
around the caveat resulting from the large amount of ancilla qubits required to
carry out the computation in the case where only generalised inverters are
used. Next, another three experiments are computed, involving cycles with a
larger state space, more specifically 16, 32 and 64 possible positions.
In order to measure the magnitude of the error of the circuit we use the cross
entropy benchmarking method, calculated through the Hellinger distance.
Finally, a derivation of the variance of the quantum walk is provided along
with a calculation of the variance for our experiment.
Quantum walks (QWs) are of interest as examples of uniquely quantum behavior and are applicable in a variety of quantum search and simulation models. Implementing QWs on quantum devices is useful from both points of view. We describe a prototype one-dimensional QW algorithm that economizes resources required in its implementation. Our algorithm needs only a single shift (increment) operation. It also allows complete flexibility in choosing the shift circuit, a resource intensive part of QW implementations. This is desirable for Noisy Intermediate-Scale Quantum (NISQ) devices, in which fewer computations implies faster execution and reduced effects of noise and decoherence. We implement versions of the algorithm, with two different shift circuit structures, on publicly accessible IBM quantum computers.
This thesis presents several quantum circuit implementations of discrete and continuous quantum walks in cycle graphs. Quantum walks have become an important tool for developing quantum algorithms, that is why this work is a contribution to the area of quantum computation, specially for scientist who want to test their developed algorithms, in a real quantum device as the IBM-Q Experience platform. We give a complete suite of quantum gates that are needed to simulate quantum walks and quantum walk-based algorithms. Since some of these quantum gates are not elementary, we show how to decompose them into fundamental quantum gates available at Qiskit, an open-source quantum computing software development framework created by IBM. This is an important contribution towards the development of a professional platform for simulating and testing quantum algorithms. We found that the decomposition of unitary gates, related to quantum walks, into elementary gates is not very well documented in the literature. We studied the efficiency of both, the number of qubits and logic gates needed for each circuit, and the correctness of the results of each experiment by comparing the theoretical expected output state with the output generated by quantum simulators. Implementations of both discrete and continuous quantum walks in quantum circuits rely heavily on controlled gates, that when decomposed into fundamental gates add a high number of quantum gates and depth. Experiments were performed on a real quantum device, but results showed that the quantum computer is not good enough when executing these quantum circuits, due to the depth of the circuits and the high amount of CNOT gates required. We tested different implementations and optimization methods for the simplification of the quantum circuits, were we find that resources grow linearly w.r.t the number of qubits, and the minimum amount of gates required for the discrete case in C8 was 144 quantum gates with a depth of 111, which is the reason of the error between the simulations and the implementations in the quantum device.
Abstract The universal quantum-walk-based quantum computation model by Childs has opened the door for a new way of studying the limitations and advantages of quantum computation, as well as for its intermediate-term simulation. In recent years, the growing interest in noisy intermediate-scale quantum (NISQ) computers has lead to intense efforts being directed at understanding the computational advantages of open quantum systems. In this work, we extend the quantum walk model to open noisy systems in order to provide such a tool for the study of NISQ computers. Our method does not use explicit purification, and allows to ignore the environment degrees of freedom and obtain a much more efficient implementation (linear rather than exponential in the runtime), which employs no ancillas, hence provides direct access to the entanglement properties of the system. In our scheme, the quantum walk amplitudes represent elements of the density matrix rather than the wavefunction of a pure state. Despite the non-trivial manifestation of the normalization requirement in this setting, we model the application of general unitary gates and nonunitary channels, with an explicit implementation protocol for channels that are commonly used in noise models.
The rotation of subspaces by a chosen angle is a fundamental quantum computing operation, with applications in error correction and quantum algorithms such as the Quantum Approximate Optimization Algorithm, the Variational Quantum Eigensolver and the quantum singular value transformation. Such rotations are usually implemented at the hardware level via multiple-controlled-phase gates, which lead to large circuit depth when decomposed into one- and two-qubit gates. Here, we propose a fast, high-fidelity way to implement such operations via topological quantum walks, where a sequence of single-qubit z rotations of an ancilla qubit are interleaved with the evolution of a system Hamiltonian in which a matrix A is embedded. The subspace spanned by the left or right singular vectors of A with non-zero singular values is rotated, depending on the state of the ancilla. This procedure can be implemented in superconducting qubits, ion-traps and Rydberg atoms with star-type connectivity, significantly reducing the total gate time required compared to previous proposals.