Quantum computing is a new computational paradigm that promises an exponential speed-up over classical algorithms. To develop efficient quantum algorithms for problems of a non-deterministic nature, random walk is one of the most successful concepts employed. In this article, we target both continuous-time and discrete-time random walk in both the classical and quantum regimes. Binary Welded Tree (BWT), or glued tree, is one of the most well-known quantum walk algorithms in the continuous-time domain. Prior work implements quantum walk on the BWT with static welding. In this context, static welding is randomized but case-specific. We propose a solution to automatically generate the circuit for the Oracle for welding. We implement the circuit using the Quantum Assembly Language, which is a language for describing quantum circuits. We then optimize the generated circuit using the Fault-Tolerant Quantum Logic Synthesis tool for any BWT instance. Automatic welding enables us to provide a generalized solution for quantum walk on the BWT.
Quantum computing is a new computational paradigm that promises an exponential speed-up over classical algorithms. To develop efficient quantum algorithms for problems of a non-deterministic nature, random walk is one of the most successful concepts employed. In this article, we target both continuous-time and discrete-time random walk in both the classical and quantum regimes. Binary Welded Tree (BWT), or glued tree, is one of the most well-known quantum walk algorithms in the continuous-time domain. Prior work implements quantum walk on the BWT with static welding. In this context, static welding is randomized but case-specific. We propose a solution to automatically generate the circuit for the Oracle for welding. We implement the circuit using the Quantum Assembly Language, which is a language for describing quantum circuits. We then optimize the generated circuit using the Fault-Tolerant Quantum Logic Synthesis tool for any BWT instance. Automatic welding enables us to provide a generalized solution for quantum walk on the BWT.
A quantum algorithm is defined by a sequence of operations that runs on a realistic model of quantum computation. Since the first quantum algorithm proposed by David Deutsch(1985), a large number of impressive quantum algorithms have been developed. Quantum random walks on a graph, which are analogous to classical stochastic walk, form the basis for some of the recent quantum algorithms that promise to significantly outperform existing classical random walk algorithms. Though research has been done on the application of quantum random walk to important computational problems, very little work has been done on its quantum circuit design. There are two types of quantum random walk algorithms: discrete-time and continuous-time. In this paper, we propose quantum circuit designs for both types of random walk algorithms that operate on various graphs. We consider in detail two important problems to which random walk algorithms are applicable: the triangle finding problem and binary welded tree problem. Though there exist a few research works related to quantum circuit design for random walk on graphs, to the best of our knowledge, the circuit designs we present here are first of their kind. We also provide an estimate of the quantum cost of these circuits for several physical machine descriptions (PMDs)of quantum systems, based on the number of quantum operations and execution cycles.
This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC’2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves certainty of success, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.
Abstract This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC'2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves certainty of success, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it is impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.
This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC'2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves zero-error, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it impossible to have a deterministic quantum algorithm with exponential speedups for the weled tree problem.
Quantum walks, being the quantum analog of classical random walks, are expected to provide a fruitful source of quantum algorithms. A few such algorithms have already been developed, including the ``glued trees'' algorithm, which provides an exponential speedup over classical methods, relative to a particular quantum oracle. Here, we discuss the possibility of a quantum walk algorithm yielding such an exponential speedup over possible classical algorithms, without the use of an oracle. We provide examples of some highly symmetric graphs on which efficient quantum circuits implementing quantum walks can be constructed and discuss potential applications to quantum search for marked vertices along these graphs.
Several prominent quantum computing algorithms—including Grover’s search algorithm and Shor’s algorithm for finding the prime factorization of an integer—employ subcircuits termed ‘oracles’ that embed a specific instance of a mathematical function into a corresponding bijective function that is then realized as a quantum circuit representation. Designing oracles, and particularly, designing them to be optimized for a particular use case, can be a non-trivial task. For example, the challenge of implementing quantum circuits in the current era of NISQ-based quantum computers generally dictates that they should be designed with a minimal number of qubits, as larger qubit counts increase the likelihood that computations will fail due to one or more of the qubits decohering. However, some quantum circuits require that function domain values be preserved, which can preclude using the minimal number of qubits in the oracle circuit. Thus, quantum oracles must be designed with a particular application in mind. In this work, we present two methods for automatic quantum oracle synthesis. One of these methods uses a minimal number of qubits, while the other preserves the function domain values while also minimizing the overall required number of qubits. For each method, we describe known quantum circuit use cases, and illustrate implementation using an automated quantum compilation and optimization tool to synthesize oracles for a set of benchmark functions; we can then compare the methods with metrics including required qubit count and quantum circuit complexity.