Mathematical models of quantum computation

In this paper, we introduce two mathematical models of realistic quantum computation. First, we develop a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation. For this purpose, we define bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation. Then, we define complexity classes EBQP, BBQP and ZBQP as counterparts of the quantum complexity classes EQP, BQP and ZQP, respectively, and show that EBQP=EQP, BBQP=BQP and ZBQP=ZQP. This implies that BQTMs are polynomially related to ordinary QTMs as long as they are used to solve decision problems. We also show that these two types of QTMs are also polynomially related when they solve a function problem which has a unique solution. Furthermore, we show that BQTMs can solve certain instances of NP-complete problems efficiently. On the other hand, in the theory of quantum computation, only feed-forward quantum circuits are investigated, because a quantum circuit represents a sequence of applications of time evolution operators. But, if a quantum computer is a physical device where the gates are interactions controlled by a current computer such as laser pulses on trapped ions, NMR and most implementation proposals, it is natural to describe quantum circuits as ones that have feedback loops if we want to visualize the total amount of the necessary hardware. For this purpose, we introduce a quantum recurrent circuit model, which is a quantum circuit with feedback loops. LetC be a quantum recurrent circuit which solves the satisfiability problem for a blackbox Boolean function includingn variables with probability at least 1/2. And lets be the size ofC (i.e. the number of the gates inC) andt be the number of iterations that is needed forC to solve the satisfiability problem. Then, we show that, for those quantum recurrent circuits, the minimum value ofmax(s, t) isO(n ²2 ^n/3). Tetsuro Nishino, D.Sc.: He is presently an Associate Professor in the Department of Information and Communication Engineering, The University of Electro-Communications. He received the B.S., M.S. and D.Sc degrees in mathematics from Waseda University, in 1982, 1984 and 1991 respectively. From 1984 to 1987, he joined Tokyo Research Laboratory, IBM Japan. From 1987 to 1992, he was a Research Associate of Tokyo Denki University, and from 1992 to 1994, he was an Associate Professor of Japan Advanced Institute of Science and Technology, Hokuriku. His main interests are circuit complexity theory, computational learning theory and quantum complexity theory.     

Classically-controlled Quantum Computation

It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically-controlled Quantum Turing Machine (CQTM) which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for a formalized classical control. In CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine is simulated by a CQTM without loss of efficiency. Furthermore, we show that any k-tape CQTM is simulated by a 2-tape CQTM with a quadratic loss of efficiency. The gap between classical and quantum computations which was already pointed out in the framework of measurement-based quantum computation (see [S. Perdrix, Ph. Jorrand, Measurement-Based Quantum Turing Machines and their Universality, arXiv, quant-ph/0404146, 2004]) is confirmed in the general case of classically-controlled quantum computation. In order to appreciate the similarity between programming classical Turing machines and programming CQTM, some examples of CQTM will be given in the full version of the paper. Proofs of lemmas and theorems are omitted in this extended abstract.     

Perfect quantum multiple-unicast network coding protocol

In order to realize long-distance and large-scale quantum communication, it is natural to utilize quantum repeater. For a general quantum multiple-unicast network, it is still puzzling how to complete communication tasks perfectly with less resources such as registers. In this paper, we solve this problem. By applying quantum repeaters to multiple-unicast communication problem, we give encoding–decoding schemes for source nodes, internal ones and target ones, respectively. Source-target nodes share EPR pairs by using our encoding–decoding schemes over quantum multiple-unicast network. Furthermore, quantum communication can be accomplished perfectly via teleportation. Compared with existed schemes, our schemes can reduce resource consumption and realize long-distance transmission of quantum information.     

Autonomous and adaptive resource allocation among multiple nodes and multiple applications in heterogeneous wireless networks

In the forthcoming future, various means of wireless communication, such as cellular, Wi-Fi, WiMAX, and DSRC, will be available to mobile users and applications. With the development of wireless communication and mobile devices, more and more users and applications will be accommodated in mobile environment. Since mobile users and applications compete for the limited wireless resources whose communication quality dynamically change, we need an adaptive mechanism for mobile users and applications to share the available network resources while satisfying each application?s QoS requirements. In this paper, we propose an adaptive resource allocation mechanism where each node autonomously determines wireless network resources to assign to each of networked applications running on it. For this purpose, we adopt an attractor composition model, which is based on an autonomous and adaptive behavior of biological systems. Through numerical analysis, we confirmed that our mechanism could adaptively and stably allocate wireless network resources to applications, while considering their QoS requirements and fairly sharing network resources with other nodes. It also is shown that our mechanism superiors to a mechanism where a node determines resource allocation by solving an optimization problem.     

Exponential Separation of Quantum and Classical Online Space Complexity

Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for the first time explicitly, space-bounded quantum algorithms for computational problems where the input is given not as a whole, but bit by bit. We show that there exist such problems that a quantum computer can solve using exponentially less work space than a classical computer. More precisely, we introduce a very natural and simple model of a space-bounded quantum online machine and prove an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. The language we consider is inspired by a communication problem (the disjointness function) that Buhrman, Cleve and Wigderson used to show an almost quadratic separation of quantum and classical bounded-error communication complexity. We prove that, in the framework of online space complexity, the separation becomes exponential.     

新量子技术时代下的信息安全

量子技术将在未来深刻影响密码学以及信息安全行业。可以利用上千个量子比特运行量子算法的通用量子计算机将直接威胁信息安全基础算法,导致当前广泛使用的RSA等公钥密码被破解,也会使分组密码算法的密码强度减半。量子通信中量子密钥分发的实施会改变传统保密通信的物理结构。这些重大 应用价值也是发展量子技术的驱动力。结合当前一些关于量子技术的热点新闻,从量子计算和量子通信两个方面分别综述了量子技术对信息安全技术的影响。同时简要介绍了这些技术的最新发展现状,包括通用型和专用型量子计算机的发展、量子密钥分发技术实验室环境的进展以及天地一体化量子通信网络的发展状况等。最后对信息安全技术的未来形态做了思考和总结。未来量子技术将会与现有各种技术深度融合,共同存在。     

The Quantum Setting with Randomized Queries for Continuous Problems

The standard setting of quantum computation for continuous problems uses deterministic queries and the only source of randomness for quantum algorithms is through measurement. Without loss of generality we may consider quantum algorithms which use only one measurement. This setting is related to the worst case setting on a classical computer in the sense that the number of qubits needed to solve a continuous problem must be at least equal to the logarithm of the worst case information complexity of this problem. Since the number of qubits must be finite, we cannot solve continuous problems on a quantum computer with infinite worst case information complexity. This can even happen for continuous problems with small randomized complexity on a classical computer. A simple example is integration of bounded continuous functions. To overcome this bad property that limits the power of quantum computation for continuous problems, we study the quantum setting in which randomized queries are allowed. This type of query is used in Shor’s algorithm. The quantum setting with randomized queries is related to the randomized classical setting in the sense that the number of qubits needed to solve a continuous problem must be at least equal to the logarithm of the randomized information complexity of this problem. Hence, there is also a limit to the power of the quantum setting with randomized queries since we cannot solve continuous problems with infinite randomized information complexity. An example is approximation of bounded continuous functions. We study the quantum setting with randomized queries for a number of problems in terms of the query and qubit complexities defined as the minimal number of queries/qubits needed to solve the problem to within ɛ by a quantum algorithm. We prove that for path integration we have an exponential improvement for the qubit complexity over the quantum setting with deterministic queries.     

Quantum computation, quantum theory and AI

The main purpose of this paper is to examine some (potential) applications of quantum computation in AI and to review the interplay between quantum theory and AI. For the readers who are not familiar with quantum computation, a brief introduction to it is provided, and a famous but simple quantum algorithm is introduced so that they can appreciate the power of quantum computation. Also, a (quite personal) survey of quantum computation is presented in order to give the readers a (unbalanced) panorama of the field. The author hopes that this paper will be a useful map for AI researchers who are going to explore further and deeper connections between AI and quantum computation as well as quantum theory although some parts of the map are very rough and other parts are empty, and waiting for the readers to fill in.     

无线Ad hoc网络中基于0-1优化的两步骤资源分配算法

为了解决无线Ad hoc网络中节点性能随节点个数增加而下降的问题,利用多射频多信道技术(MR-MC)进行资源分配以及减少网络干扰量已成为优化无线网络性能的重要技术手段。在此基础上,提出了一种基于0-1规划的网络优化模型和两步骤资源分配算法TBCA&LS(Tree Based Channel Assignment&Link Scheduling)。该算法利用分簇重组网络结构,通过分析相邻链路干扰关系构建0-1优化模型,并在此基础上执行将信道分配和链路调度结合的资源分配算法,减少相邻链路冲突,增加并行传输量,进而达到提升网络吞吐量、优化网络资源分配的目的。最后,在Matlab仿真软件中执行两步骤资源分配算法,实验结果表明,与对比算法CCAS和仅利用信道分配的算法相比,所提算法可以有效优化网络性能。     

量子计算机进入实验阶段

首先简要介绍分层计算的制约;其次介绍最近量子信息的开发,在理论和实践两方面的通信和计算,诸如量子逻辑门、量子密码学、量子交缠性、超距传输的实验性实现、量子算法的首次实验性实现、量子因子分解、量子纪错码以及基于硅片的原子自旋量子计算机;最后讨论克服非相干性困难的方法。     

A general method for avoiding cycling in a network

In this article we consider the problem of finding a simple path between two nodes of a network using a limited local search. A simple path is one which contains no cycles. The network is assumed to reside in the Euclidean plane, although it may not necessarily be planar in the usual graph-theoretic sense. The algorithm that we shall present features two parameters which limit the search for a simple path. These parameters may be adjusted to increase the probability that a simple path will be found (at the expense of higher computation costs). One application of this algorithm is in finding alternative routes in a partially damaged communications network.     

QKD网络量子信道管理关键技术研究

随着网络的发展,网络传播的信息日益增多,其中某些信息需要较高的安全性,因此信息加密手段的研究具有重大意义。量子密钥分发(Quantum Key Distribution,QKD)技术基于量子力学中的不可克隆定理,即不可能复制一个未知的量子态而不对其造成扰动,保证了其无条件的安全性,能够实现安全的密钥分发。但目前QKD网络规模较小,不能满足大规模组网的需求。同时,经典网络的路由技术已经不能适应QKD网络,量子信道寻径成为了一个需要解决的问题。鉴于以上问题,提出了一种能够满足较大规模QKD通信的基于光开关切换的QKD网络模型,并重点设计了其网络结构和信令体系,在此基础上设计了一个用于量子信道寻径的先导信号协议,并提出了量子信道管理机制。经实验验证,该模型的性能良好。     

An improved multiobjective approach inspired by the flashing behaviour of fireflies for Traffic Grooming in optical WDM networks

Nowadays, the traffic demands in optical networks are low-speed traffic requests (low bandwidth requirement of a few Mbps) that employ the huge capacity of a fiber channel (Gbps), causing a waste of bandwidth as a result. Fortunately, by using electronic grooming nodes, we can multiplex (groom) several low-speed demands onto one channel in order to optimize the available resources in an optical network. The problem of grooming low-speed traffic requests is known in the literature as the Traffic Grooming problem and is considered an NP-hard optimization problem. In this work, we use both multiobjective optimization and evolutionary computation with the aim of facing this optical networking problem. The selected evolutionary algorithm is based in the behaviour of fireflies, the Firefly Algorithm (FA). In order to optimize more than one conflicting objective function of the Traffic Grooming problem simultaneously, we have modified the standard FA to the multiobjective domain (MO-FA). After carrying out different experiments with diverse real-world optical networks, comparing the results of the MO-FA with other multiobjective approaches and different standard heuristics for this problem, we can conclude saying that the new version of the MO-FA is an effective approach for dealing with this telecommunication problem.     

Certificateless network coding proxy signatures from lattice

Network coding can improve the information transmission efficiency and reduces the network resource consumption, so it is a very good platform for information transmission. Certificateless proxy signatures are widely applied in information security fields. However, certificateless proxy signatures based on classical number theory are not suitable for the network coding environment and cannot resist the quantum computing attacks. In view of this, we construct certificateless network coding proxy signatures from lattice (LCL-NCPS). LCL-NCPS is new multi-source signature scheme which has the characteristics of anti-quantum, anti-pollution and anti-forgery. In LCL-NCPS, each source node user can output a message vector to intermediate node and sink node, and the message vectors from different source nodes will be linearly combined to achieve the aim of improving the network transmission rate and network robustness. In terms of efficiency analysis of space dimension, LCL-NCPS can obtain the lower computation complexity by reducing the dimension of proxy key. In terms of efficiency analysis of time dimension, LCL-NCPS has higher computation efficiency in signature and verification.     

单层量子感知器网络及其性能

目前人工智能的体系结构普遍比较复杂,所以它的广泛应用受到了很大的限制.利用量子计算的一些优点特别是量子并行计算特性提出一个单层量子感知器网络,该网络充分利用量子相位,使得它具有传统的单层感知器所无法具有的计算能力.对单层量子感知器进行实例分析、性能分析和仿真实验,表明单神经元量子感知器能实现单神经元经典感知器无法实现的XOR功能.即简单的网络结构实现了相对复杂的网络功能,这一特点有利于降低网络体系结构的复杂性,它必将对人工智能和控制领域的研究产生重大的影响.     

Timing of resources exploration in the behavior of firm – Innovative approach and empirical simulation

We have insight into the importance of resource exploration derived from the quest for sustaining competitive advantage as well as the growth of the firm, which are well-explicated in the resources point of view. However, we really do not know when the firm will seriously commit to this kind of activities. Therefore, this study proposes an innovative approach using quantum minimization (QM) to tune a composite model comprising adaptive neuron-fuzzy inference system (ANFIS) and nonlinear generalized autoregressive conditional heteroscedasticity (NGARCH) such that it constitutes the relationship among five indicators, the growth rate of long-term investment, the firm size, the return on total asset, the return on common equity, and the return on sales. In particularly, this proposed approach outperforms several typical methods such as auto-regressive moving-average regression (ARMAX), back-propagation neural network (BPNN), or adaptive support vector regression (ASVR) for this timing problem in term of comparing their achievement and the goodness-of-fit. Consequently, the preceding methods involved in this problem truly explain the timing of resources exploration in the behavior of firm. Meanwhile, the performance summary among methods is compared quantitatively.     

Nonlocal quantum information in bipartite quantum error correction

We show how to convert an arbitrary stabilizer code into a bipartite quantum code. A bipartite quantum code is one that involves two senders and one receiver. The two senders exploit both nonlocal and local quantum resources to encode quantum information with local encoding circuits. They transmit their encoded quantum data to a single receiver who then decodes the transmitted quantum information. The nonlocal resources in a bipartite code are ebits and nonlocal information qubits, and the local resources are ancillas and local information qubits. The technique of bipartite quantum error correction is useful in both the quantum communication scenario described above and in fault-tolerant quantum computation. It has application in fault-tolerant quantum computation because we can prepare nonlocal resources offline and exploit local encoding circuits. In particular, we derive an encoding circuit for a bipartite version of the Steane code that is local and additionally requires only nearest-neighbor interactions. We have simulated this encoding in the CNOT extended rectangle with a publicly available fault-tolerant simulation software. The result is that there is an improvement in the “pseudothreshold” with respect to the baseline Steane code, under the assumption that quantum memory errors occur less frequently than quantum gate errors.     

基于序列输入的量子神经网络模型及算法

为提高神经网络的逼近能力,提出一种各维输入为离散序列的量子神经网络模型及算法.该模型为3层结构,隐层为量子神经元,输出层为普通神经元.量子神经元由量子旋转门和多位受控非门组成,利用多位受控非门中目标量子位的输出向输入端的反馈,实现对输入序列的整体记忆,利用受控非门输出中多位量子比特的纠缠获得量子神经元的输出.基于量子计算理论设计该模型的学习算法.该模型可从宽度和深度两方面获取输入序列的特征.仿真结果表明,当输入节点数和序列长度满足一定关系时,该模型明显优于普通神经网络.     

Binary image denoising using a quantum multilayer self organizing neural network

Several classical techniques have evolved over the years for the purpose of denoising binary images. But the main disadvantages of these classical techniques lie in that an a priori information regarding the noise characteristics is required during the extraction process. Among the intelligent techniques in vogue, the multilayer self organizing neural network (MLSONN) architecture is suitable for binary image preprocessing tasks.In this article, we propose a quantum version of the MLSONN architecture. Similar to the MLSONN architecture, the proposed quantum multilayer self organizing neural network (QMLSONN) architecture comprises three processing layers viz., input, hidden and output layers. The different layers contains qubit based neurons. Single qubit rotation gates are designated as the network layer interconnection weights. A quantum measurement at the output layer destroys the quantum states of the processed information thereby inducing incorporation of linear indices of fuzziness as the network system errors used to adjust network interconnection weights through a quantum backpropagation algorithm.Results of application of the proposed QMLSONN are demonstrated on a synthetic and a real life binary image with varying degrees of Gaussian and uniform noise. A comparative study with the results obtained with the MLSONN architecture and the supervised Hopfield network reveals that the QMLSONN outperforms the MLSONN and the Hopfield network in terms of the computation time.     

The optimization landscape of hybrid quantum–classical algorithms: From quantum control to NISQ applications

This review investigates the landscapes of hybrid quantum–classical optimization algorithms that are prevalent in many rapidly developing quantum technologies, where the objective function is computed by either a natural quantum system or an engineered quantum ansatz, but the optimizer is classical. In any particular case, the nature of the underlying control landscape is fundamentally important for systematic optimization of the objective. In early studies on the optimal control of few-body dynamics, the optimizer could take full control of the relatively low-dimensional quantum systems to be manipulated. Stepping into the noisy intermediate-scale quantum (NISQ) era, the experimentally growing computational power of the ansatz expressed as quantum hardware may bring quantum advantage over classical computers, but the classical optimizer is often limited by the available control resources. Across these different scales, we will show that the landscape’s geometry experiences morphological changes from favorable trap-free landscapes to easily trapping rugged landscapes, and eventually to barren-plateau landscapes on which the optimizer can hardly move. This unified view provides the basis for understanding classes of systems that may be readily controlled out to those with special consideration, including the difficulties and potential advantages of NISQ technologies, as well as seeking possible ways to escape traps or plateaus, in particular circumstances.