Quantum computers exploits quantum entanglement and provides more computing power. Duality quantum computer is a new type of quantum computer that exploits the particle wave duality of quantum mechanics. In a duality computer, the computing gates need not be unitary. This provides more flexibility and familiarity to computer scientists. Here we use the unsorted database search problem as an example to show how to construct search algorithms in quantum computer and duality quantum computers.
Quantum computers exploits quantum entanglement and provides more computing power. Duality quantum computer is a new type of quantum computer that exploits the particle wave duality of quantum mechanics. In a duality computer, the computing gates need not be unitary. This provides more flexibility and familiarity to computer scientists. Here we use the unsorted database search problem as an example to show how to construct search algorithms in quantum computer and duality quantum computers.
Quantum mechanics possesses peculiar properties that is hard to comprehend with mundane experience. Exploiting the quantum properties of quantum systems, quantum computer can provide more computing power than classical computer. Duality quantum computer, or duality computer for short, is a new type of quantum computer that exploits the particle wave duality of quantum mechanics. In a duality computer, the computing gates, or generalized quantum gates, need not be unitary. Thus duality computer provides a novel paradigm for quantum computing, and may bring new computing power. In addition, it provides flexibility in computing gates design that is familiar to computer scientists. Here we review the basic concepts of duality quantum computing and give some examples.
Quantum computing exploits quantum mechanical properties to perform computations. It enables quantum parallelism and provides much more powerful data processing capabilities than classical computers. With a quantum computer, one can exponentially accelerate quantum system simulation and accelerate some important classical algorithms. Traditional quantum algorithms use unitary evolution to process information. A quantum computing process is the product of a series of unitary operators. In 1994, Shor invented a quantum prime factorization algorithm that exponentially accelerates the factorization of an integer. In 1996, Grover proposed a quantum search algorithm that accelerates the search of an unsorted database using square-root steps. Afterwards, the development of quantum algorithms slowed down, leading to a subsequent query by Shor in 2003 regarding why no more significant quantum algorithms have been found. Since 2009, many important new quantum algorithms have been proposed, such as a quantum algorithm for solving linear equations with the capability of exponential acceleration, a quantum algorithm for sparse Hamiltonian simulation using linear combinations of unitary operators, and a novel algorithm for Hamiltonian simulation, which provides exponential improvements in precision. In this paper, we first describe the basic principles of quantum computation. We then describe the Shor algorithm and Grover/Long search algorithm. These quantum algorithms are the general quantum algorithms that use unitary operations in their computational processes. Next, we introduce the basic principles of duality quantum computing, which was proposed in 2002. In contrast to traditional quantum computing, duality quantum computing allows the use of linear combinations of unitary operators in the computation process, meaning the multiplication, division, addition, and subtraction of unitary operators are all possible in duality quantum computing. Thus, duality quantum computing provides more flexibility for constructing quantum algorithms and the techniques used in classical algorithm design can be directly used to construct quantum algorithms. We then review recent work regarding newer quantum algorithms that enable the linear combination of unitary operators, which are actually duality quantum algorithms. Additionally, a duality quantum simulation algorithm for open quantum systems is introduced. This algorithm not only reduces computational complexity, but also improves accuracy exponentially. Finally, a summary and the future prospects of quantum algorithms are provided.
In this summary we discuss two new algorithms for Grover's unsorted database search problem that claimed to have reached exponential speedup over Grover's original algorithm. One is in the quantum setting with "power queries" that allow for exponential reduction in the number of queries over Grover's original algorithm with "bit queries". The other is to use "dubit queries" on a duality computer - a new computing model uses a quantum system's wave-particle duality, which is able to achieve even greater computing power and better capability than existent quantum computers we have been discussing. We discuss the shortages and difficulties of both schemes as well.
In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both classical computer and the quantum computer. According to the general principle of quantum interference, the very essence of quantum interference is the interference of the sub-waves of the quantum system itself. A quantum system considered here can be any quantum system: a single microscopic particle, a composite quantum system such as an atom or a molecule, or a loose collection of a few quantum objects such as two independent photons. In the duality computer, the wave of the duality computer is split into several sub-waves and they pass through different routes, where different computing gate operations are performed. These sub-waves are then re-combined to interfere to give the computational results. The quantum computer, however, has only used the particle nature of quantum object. In a duality computer, it may be possible to find a marked item from an unsorted database using only a single query, and all NP-complete problems may have polynomial algorithms. Two proof-of-the-principle designs of the duality computer are presented: the giant molecule scheme and the nonlinear quantum optics scheme. We also propose thought experiment to check the related fundamental issues, the measurement efficiency of a partial wave function.
Quantum computers are proven to be more efficient at solving a specific class of problems compared to traditional digital computers. Superposition of states and quantum entanglement are the two key ingredients that make quantum computing so powerful. However, not all quantum algorithms require quantum entanglement (e.g., search through an unsorted database). Is it possible to utilize classical wave superposition to speed up database searching as much as by using quantum computers? There were several attempts to mimic quantum computers using classical waves. It was concluded that the use of classical wave superposition comes with the cost of an exponential increase in resources. In this work, we consider the feasibility of building classical wave-based devices able to provide fundamental speedup over digital counterparts without the exponential overhead. We present experimental data on database searching through a magnetic database using spin wave superposition. The results demonstrate the same speedup as expected for quantum computers. Also, we present examples of numerical modeling demonstrating classical wave interference for period finding. This approach may not compete with quantum computers with efficiency but outperform classical digital computers. We argue that classical wave-based devices can perform some of the quantum algorithms with the same efficiency as quantum computers as long as quantum entanglement is not required.
The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.