Quantum computation: Algorithms and Applications

As the prospect of commercial quantum computers turns ever more real in recent times, research in quantum algorithms becomes the center of attention. Due to the strong parallelism of quantum computing in Hilbert space, ordinarily intractable calculation problems could now be solved very efficiently with non-classical means. To exploit parallelism, creative quantum algorithms are required so that efficient quantum oracles can be tailor-designed to specific computation needs. Therefore, in the quest for quantum supremacy, quantum algorithms and their related applications are as important as the quantum computer hardware. This article covers the basic concepts of quantum computation and reviews some important quantum algorithms and their applications.     

Photonic Implementation of Quantum Computation Algorithm Based on Spatial Coding

Several implementation methods of quantum computation algorithm by conventional computer have been explored for large-scale emulation. Due to the lack of quantum effects, these methods generally require exponential growth of the size of the hardware with increase of the number of qubits. In this paper, the spatial coding, which is an effective digital optical computing technique, is studied as an efficient implementation method of quantum computation algorithms. In the proposed scheme, quantum information is represented by the intensity and the phase of elemental cells. We confirmed correct operation of the quantum teleportation algorithm by computer simulation. We also demonstrated a photonic implementation of some of the quantum gates experimentally.     

Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation

Recent development of computer technology may lead to the quantum image algorithms becoming a hotspot. Quantum information and computation give some advantages to our quantum image algorithms, which deal with the limited problems that cannot be solved by the original classical image algorithm. Image processing cry out for applications of quantum image. Most works on quantum images are theoretical or sometimes even unpolished, although real-world experiments in quantum computer have begun and are multiplying. However, just as the development of computer technology helped to drive the Technology Revolution, a new quantum image algorithm on constrained least squares filtering computation was proposed from quantum mechanics, quantum information, and extremely powerful computer. A quantum image representation model is introduced to construct an image model, which is then used for image processing. Prior knowledge is employed in order to reconstruct or estimate the point spread function, and a non-degenerate estimate is obtained based on the opposite processing. The fuzzy function against noises is solved using the optimal measure of smoothness. On the constraint condition, determine the minimum criterion function and estimate the original image function. For some motion blurs and some kinds of noise pollutions, such as Gaussian noises, the proposed algorithm is able to yield better recovery results. Additionally, it should be noted that, when there is a noise attack with very low noise intensity, the model based on the constrained least squares filtering can still deliver good recovery results, with strong robustness. Subsequently, discuss the simulation analysis of the complexity of implementing quantum circuits and image filtering, and demonstrate that the algorithm has a good effect on fuzzy recovery, when the noise density is small.     

Realizing number recognition with simulated quantum semi-restricted Boltzmann machine

Quantum machine learning based on quantum algorithms may achieve an exponential speedup over classical algorithms in dealing with some problems such as clustering. In this paper, we use the method of training the lower bound of the average log likelihood function on the quantum Boltzmann machine (QBM) to recognize the handwritten number datasets and compare the training results with classical models. We find that, when the QBM is semi-restricted, the training results get better with fewer computing resources. This shows that it is necessary to design a targeted algorithm to speed up computation and save resources.     

Quantum computation and error correction based on continuous variable cluster states

Measurement-based quantum computation with continuous variables, which realizes computation by performing measurement and feedforward of measurement results on a large scale Gaussian cluster state, provides a feasible way to implement quantum computation. Quantum error correction is an essential procedure to protect quantum information in quantum computation and quantum communication. In this review, we briefly introduce the progress of measurement-based quantum computation and quantum error correction with continuous variables based on Gaussian cluster states. We also discuss the challenges in the fault-tolerant measurement-based quantum computation with continuous variables.     

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.     

A prototype of quantum von Neumann architecture

A modern computer system, based on the von Neumann architecture, is a complicated system with several interactive modular parts. It requires a thorough understanding of the physics of information storage, processing, protection, readout, etc. Quantum computing, as the most generic usage of quantum information, follows a hybrid architecture so far, namely, quantum algorithms are stored and controlled classically, and mainly the executions of them are quantum, leading to the so-called quantum processing units. Such a quantum–classical hybrid is constrained by its classical ingredients, and cannot reveal the computational power of a fully quantum computer system as conceived from the beginning of the field. Recently, the nature of quantum information has been further recognized, such as the no-programming and no-control theorems, and the unifying understandings of quantum algorithms and computing models. As a result, in this work, we propose a model of a universal quantum computer system, the quantum version of the von Neumann architecture. It uses ebits (i.e. Bell states) as elements of the quantum memory unit, and qubits as elements of the quantum control unit and processing unit. As a digital quantum system, its global configurations can be viewed as tensor-network states. Its universality is proved by the capability to execute quantum algorithms based on a program composition scheme via a universal quantum gate teleportation. It is also protected by the uncertainty principle, the fundamental law of quantum information, making it quantum-secure and distinct from the classical case. In particular, we introduce a few variants of quantum circuits, including the tailed, nested, and topological ones, to characterize the roles of quantum memory and control, which could also be of independent interest in other contexts. In all, our primary study demonstrates the manifold power of quantum information and paves the way for the creation of quantum computer systems in the near future.     

量子信息光学

介绍了一门新的学科分支－量子信息光学。它是量子光学与信息科学相结合的产物。光场的量子效应在实现大容量的信息传输，超高精度的信息检测以及不可破译、不可窃听的量子密码术方面有着极其重要的应用前景，在光子学的发展中将发挥独特的作用。该文阐述了量子信息光学中若干物理问题和研究方向，包括超低噪声光源、量子信息复制、量子态工程、量子非破坏性测量和量子密码术。     

Statistical physics of hard combinatorial optimization:Vertex cover problem

Typical-case computation complexity is a research topic at the boundary of computer science, applied mathematics,and statistical physics. In the last twenty years, the replica-symmetry-breaking mean field theory of spin glasses and the associated message-passing algorithms have greatly deepened our understanding of typical-case computation complexity.In this paper, we use the vertex cover problem, a basic nondeterministic-polynomial(NP)-complete combinatorial optimization problem of wide application, as an example to introduce the statistical physical methods and algorithms. We do not go into the technical details but emphasize mainly the intuitive physical meanings of the message-passing equations. A nonfamiliar reader shall be able to understand to a large extent the physics behind the mean field approaches and to adjust the mean field methods in solving other optimization problems.     

量子信息引论

文章在阐述量子信息的发展背景之后,介绍了量子纠缠、量子计算、量子密码、量子因特网、量子克隆、量子对策论等方面的内容,既阐述了相关的基本概念,也论及最新的研究进展。     

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a "duality computer" and show its advantage over other algorithms.     

General Quantum Interference Principle and Duality Computer

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.     

量子开系统理论及其应用

量子物理是当代科学发展的基石,多次引发高技术革命.它与信息科学结合,产生了交叉学科——量子信息,为突破计算机芯片的尺度极限提供了全新的解决思路.自1987年起,文章作者及其合作者对量子开系统理论、量子退相干及其相关的量子物理基本问题进行了系统的探索,契合了最近10年量子信息研究的快速发展.文章首先结合上世纪70年代末彭桓武先生关于量子开系统(阻尼谐振子的量子化)的重要研究工作,介绍了量子开系统的基本概念及其研究的科学意义,同时简略介绍了文章作者及其合作者在量子开系统理论及其在量子信息应用方面的系列研究工作.     

Quantum Algorithms for Some Well—Known NP Problems

It is known that quantum computer is more powerful than classical computer.In this paper we present quantum algorithms for some famous NP problems in graph theory and combination theory,these quantum algorithms are at least quadratically faster than the classical ones.     

Computing the non-computable

We explore in the framework of quantum computation the notion of computability, which holds a central position in mathematics and theoretical computer science. A quantum algorithm that exploits the quantum adiabatic processes is considered for Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically non-computable. Generalized quantum algorithms are also considered for some other mathematical non-computables in the same and in different non-computability classes. The key element of all these algorithms is the measurability of both the values of physical observables and the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of mathematics, ought to be determined not solely by mathematics itself but also by physical principles.     

量子信息与计算

量子信息与计算是物理学目前研究的热门领域 .本文简要地介绍量子计算的一些基本概念 :量子纠缠、量子位、量子寄存器、量子并行计算和量子纠错 .并介绍两种典型的量子信息技术 :量子密码和量子传物 .     

Scalable quantum information processing and the optical topological quantum computer

Optical quantum computation has represented one of the most successful testbed systems for quantum information processing. Along with ion-traps and nuclear magnetic resonance (NMR), experimentalists have demonstrated control of qubits, multi-gubit gates and small quantum algorithms. However, photonic based qubits suffer from a problematic lack of a large scale architecture for fault-tolerant computation which could conceivably be built in the near future. While optical systems are, in some regards, ideal for quantum computing due to their high mobility and low susceptibility to environmental decoherence, these same properties make the construction of compact, chip based architectures difficult. Here we discuss many of the important issues related to scalable fault-tolerant quantum computation and introduce a feasible architecture design for an optics based computer. We combine the recent development of topological cluster state computation with the photonic module, simple chip based devices which can be utilized to deterministically entangle photons. The integration of this operational unit with one of the most exciting computational models solves many of the existing problems with other optics based architectures and leads to a feasible large scale design which can continuously generate a 3D cluster state with a photonic module resource cost linear in the cross sectional size of the cluster.     

Noisy intermediate-scale quantum computers

Quantum computers have made extraordinary progress over the past decade, and significant milestones have been achieved along the path of pursuing universal fault-tolerant quantum computers. Quantum advantage, the tipping point heralding the quantum era, has been accomplished along with several waves of breakthroughs. Quantum hardware has become more integrated and architectural compared to its toddler days. The controlling precision of various physical systems is pushed beyond the fault-tolerant threshold. Meanwhile, quantum computation research has established a new norm by embracing industrialization and commercialization. The joint power of governments, private investors, and tech companies has significantly shaped a new vibrant environment that accelerates the development of this field, now at the beginning of the noisy intermediate-scale quantum era. Here, we first discuss the progress achieved in the field of quantum computation by reviewing the most important algorithms and advances in the most promising technical routes, and then summarizing the next-stage challenges. Furthermore, we illustrate our confidence that solid foundations have been built for the fault-tolerant quantum computer and our optimism that the emergence of quantum killer applications essential for human society shall happen in the future.     

Implementing Classical Hadamard Transform Algorithm by Continuous Variable Cluster State

Measurement-based one-way quantum computation, which uses cluster states as resources, provides an efficient model to perform computation. However, few of the continuous variable(CV) quantum algorithms and classical algorithms based on one-way quantum computation were proposed. In this work, we propose a method to implement the classical Hadamard transform algorithm utilizing the CV cluster state. Compared with classical computation, only half operations are required when it is operated in the one-way CV quantum computer. As an example, we present a concrete scheme of four-mode classical Hadamard transform algorithm with a four-partite CV cluster state. This method connects the quantum computer and the classical algorithms, which shows the feasibility of running classical algorithms in a quantum computer efficiently.