Advanced Intelligent Systems

A New Type of Classical Logic Circuit with Exponential Speedup

Yingji Zhang, Tian Chen, Xiaoxue Tong, Naiqiao Pan, Xiangdong Zhang

Published Jan 19, 2023• 9 citations

Abstract

Compared with classical algorithms, quantum algorithms can show the advantage of exponential speedup in solving some problems. Solving the NAND‐Tree problem is a typical example, which can be speed up exponentially by quantum walk. This scheme is groundbreaking due to the universality of the negative‐AND (NAND) gate. In fact, the NAND gate is also universal for classical computation, making it an important target for development. Herein, the quantum NAND‐Tree onto the classical circuit network is mapped and a new type of classical logic circuit with the NAND gate that can perform the quantum algorithms is designed. These classical logic gates that are designed have exponential speedup functions compared with conventional ones. Because classical circuit networks possess good scalability and stability, the present scheme is expected to have potential applications for information processing in the era of big data.

DOI: 10.1002/aisy.202200232

Related papers

Quantum Combinational Logics and their Realizations with Circuits

Xiaoxue Tong, Tian Chen, Naiqiao Pan +1 more

Abstract Classical combinational logic circuits (CCLCs) are widely used in various fields. Corresponding to the CCLCs, here schemes are given for some quantum combinational logic circuits (QCLCs) based on the quantum NAND tree. Three typical circuits, adder, comparator, and seven‐segment display decoder, are discussed in detail as examples. All the designs of the schemes are based on the quantum random walk theory. Furthermore, these QCLCs are mapped onto the classical circuit networks and design new types of CCLCs, and take advantage of the fact that there is a good correspondence between the voltage in the circuit satisfying Kirchhoff's law and the system wave function satisfying the Schrodinger equation. These CCLCs that are designed have exponential speedup functions compared with conventional ones, which have been demonstrated experimentally. Because classical circuit networks possess good scalability and stability, the realization of QCLCs on classical circuits is expected to have potential applications for information processing in the era of big data.

Advanced Quantum TechnologiesOct 15, 20234 citations

Electric‐Circuit Simulation of Quantum Fast Hitting with Exponential Speedup

Hanxu Zhang, Tian Chen, Naiqiao Pan +1 more

Abstract The ultimate goal of developing quantum algorithms and constructing quantum computers is to achieve faster information processing than using current classical computers. Quantum walks are powerful kernels in quantum computing protocols and possess strong capabilities in speeding up various simulation and optimization tasks. One striking example is provided by quantum walkers evolving on unbalanced trees, which demonstrate faster hitting performances than classical random walk. However, direct experimental construction of unbalanced trees to prove quantum advantage with exponential speedup remains a great challenge due to the highly complex arrangements of the structure. This study attempts to simulate quantum algorithm by classical circuit. Inspired by the quantum algorithm, the classical circuit networks are designed and fabricated with unbalanced tree structures. It is then demonstrated, both theoretically and experimentally, that the quantum algorithm for the fast hitting problem can be simulated in the structure. It is shown that the hitting efficiency of electric signals in the circuit networks with unbalanced tree structures is exponentially faster than the corresponding cases of classical random walks. Because classical circuit networks possess good scalability and stability, the results open up a scalable new path toward quantum speedup in complex problems.

Advanced Quantum TechnologiesFeb 5, 202216 citations

Efficient circuit implementation for coined quantum walks on binary trees and application to reinforcement learning

Thomas Mullor, David Vigouroux, Louis Béthune

Quantum walks on binary trees are used in many quantum algorithms to achieve important speedup over classical algorithms. The formulation of this kind of algorithms as quantum circuit presents the advantage of being easily readable, executable on circuit based quantum computers and simulators and optimal on the usage of resources. We propose a strategy to compose quantum circuit that performs quantum walk on binary trees following universal gate model quantum computation principles. We give a particular attention to NAND formula evaluation algorithm as it could have many applications in game theory and reinforcement learning. We therefore propose an application of this algorithm and show how it can be used to train a quantum reinforcement learning agent in a two player game environment.

arXiv:2210.06784IEEE/ACM Symposium on Edge Computing (SEC)Dec 1, 20221 citation

Can quantum walks provide practical exponential speedups

B. L. Douglas, Jingbo B. Wang

Quantum walks, being the quantum analogue 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.

Jun 3, 20071 citation

Efficient quantum circuit implementation of quantum walks

B. L. Douglas, Jingbo B. Wang

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.

arXiv:0706.0304Physical Review AMay 27, 200998 citations

Electric-Circuit Realization of Fast Quantum Search

Naiqiao Pan, Tian Chen, Houjun Sun +1 more

Quantum search algorithm, which can search an unsorted database quadratically faster than any known classical algorithms, has become one of the most impressive showcases of quantum computation. It has been implemented using various quantum schemes. Here, we demonstrate both theoretically and experimentally that such a fast search algorithm can also be realized using classical electric circuits. The classical circuit networks to perform such a fast search have been designed. It has been shown that the evolution of electric signals in the circuit networks is analogies of quantum particles randomly walking on graphs described by quantum theory. The searching efficiencies in our designed classical circuits are the same to the quantum schemes. Because classical circuit networks possess good scalability and stability, the present scheme is expected to avoid some problems faced by the quantum schemes. Thus, our findings are advantageous for information processing in the era of big data.

ResearchJan 1, 202130 citations