All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

Quantum Neural Networks
Sanjay Gupta
Department of Computer Science
Virginia Polytechnic Institute and State University
7054 Haycock Rd.
Falls Church VA 22043-2311
Telephone: (703) 538-8373
Fax: (703) 538-8348
email: sgupta@vt.edu
R.K.P. Zia
Department of Physics
Virginia Polytechnic Institute and State University
Blacksburg, VA 24061-0435
email: rkpzia@vt.edu
February 23, 2001
Abstract
This paper initiates the study of quantum computing within the constraint

Tags

Transcript

Quantum Neural Networks
Sanjay GuptaDepartment of Computer ScienceVirginia Polytechnic Institute and State University7054 Haycock Rd.Falls Church VA 22043-2311Telephone: (703) 538-8373Fax: (703) 538-8348email: sgupta@vt.eduR.K.P. ZiaDepartment of PhysicsVirginia Polytechnic Institute and State UniversityBlacksburg, VA 24061-0435email: rkpzia@vt.eduFebruary 23, 2001
Abstract
This paper initiates the study of quantum computing within the constraints of using a polylog-arithmic (
O
(log
k
n
)
,k
≥
1) number of qubits and a polylogarithmic number of computation steps.The current research in the literature has focussed on using a polynomial number of qubits. A newmathematical model of computation called
Quantum Neural Networks (QNNs)
is deﬁned, buildingon Deutsch’s model of quantum computational network. The model introduces a nonlinear andirreversible gate, similar to the speculative operator deﬁned by Abrams and Lloyd. The precisedynamics of this operator are deﬁned and while giving examples in which nonlinear Schr¨odinger’sequations are applied, we speculate on its possible implementation. The many practical problemsassociated with the current model of quantum computing are alleviated in the new model. It isshown that QNNs of logarithmic size and constant depth have the same computational power asthreshold circuits, which are used for modeling neural networks. QNNs of polylogarithmic sizeand polylogarithmic depth can solve the problems in NC, the class of problems with theoreticallyfast parallel solutions. Thus, the new model may indeed provide an approach for building scalableparallel computers.
Key Words:
theoretical computer science; parallel computation; quantum computing; Church-Turing thesis; threshold circuits.
1 Introduction
The concept of quantum computing, based on the quantum mechanical nature of physical reality,is ﬁrst stated by Benioﬀ [5] and Feynman [15], and formalized by Deutsch [13], Bernstein andVazirani [8], and Yao [42]. For background material, the reader is referred to the papers mentionedabove, survey papers [2, 9, 33, 38], books [18, 41], and courses available on the web [29, 40].Considerable interest has been generated in quantum computing since Shor [37] showed thatnumbers can be factored in polynomial time on a quantum computer. From a practical viewpoint,Shor’s result shows that a working quantum computer can violate the security of transactionsthat use the RSA protocol, a standard for secure transactions on the Internet. From a theoreticalviewpoint, the result seemingly violates the polynomial version of the Church-Turing thesis; itis generally believed that factoring cannot be done in polynomial time on a deterministic orprobabilistic Turing machine. What makes Shor’s breakthrough result possible on a quantumTuring machine is that exponentially many computations can be performed in parallel in one stepand certain quantum steps enable one to extract the desired information.Even though simple quantum computers have been built, enormous practical issues remainfor larger-scale machines. The problems seem to be exacerbated with more qubits and more com-putation steps. In this paper, we initiate the study of quantum computing within the constraintsof using a polylogarithmic (
O
(log
k
n
)
,k
≥
1) number of qubits and a polylogarithmic number of computation steps. The current research in the literature has focussed on using a polynomialnumber of qubits. (Recently, researchers have initiated the study of quantum computing using apolynomial number of qubits and a polylogarithmic number of steps [28, 27, 17, 12].) We deﬁne anew mathematical model of computation called
Quantum Neural Networks (QNNs)
, building onDeutsch’s model of quantum computational network [14]. The new model introduces a nonlinear,irreversible, and dissipative operator, called
D
gate, similar to the speculative operator introducedby Abrams and Lloyd [1]. We also deﬁne the precise dynamics of this operator and while givingexamples in which nonlinear Schr¨odinger’s equations are applied, we speculate on the possibleimplementation of the
D
gate.Within a general framework of size, depth, and precision complexity, we study the compu-tational power of QNNs. We show that QNNs of logarithmic size and constant depth have thesame computational power as threshold circuits, which are used for modeling neural networks.QNNs of polylogarithmic size and polylogarithmic depth can solve the problems in NC, the classof problems that have theoretically fast parallel solutions. Thus, the new model subsumes thecomputation power of various theoretical models of parallel computation.We believe that the true advantage of quantum computation lies in overcoming the commu-nication bottleneck that has plagued the implementation of various theoretical models of parallelcomputation. For example, NC circuits elegantly capture the class of problems that can be theo-retically solved fast in parallel using simple gates. While fast implementations of individual gateshave been achieved with semiconductors and millions of gates have been put on a single chip, wedo not have the implementation of full NC circuits because of the communication and synchro-nization costs involved in wiring a polynomial number of gates. We believe that this hurdle canbe overcome using the nonlocal interactions present in quantum systems — there is no need toexplicitly wire the entangled units and the synchronization is instantaneous. This advantage ismanifest in the standard unitary operator, where operations on one qubit can aﬀect probabilityamplitudes on all the qubits, without requiring explicit physical connections and a global clock.1
10X
U
Source gates Sink gateLocal unitary operator
Figure 1: Components of Deutsch’s quantum computational network modelThus, the new model has the potential to overcome the practical problems associated with bothquantum computing as well as classical parallel computing.The paper addresses three categories of researchers: complexity theory, neural networks, andquantum computing. For complexity theorists, the paper shows that the 2
log
O
(1)
n
bounds onthreshold circuits obtained in various results such as [3] is not necessarily infeasible. (Polynomialtime and space is generally accepted as deﬁning feasible bounds.) For neural network researchers,the paper mathematically proves that threshold circuits used for modeling neural networks havethe same computation power as the equality threshold circuits, introduced in this paper. The newclass has certain algebraic advantages and it may indeed be beneﬁcial to redo the theory of neuralnetworks under this model. Finally, for quantum computing researchers, the paper shows thatwith quantum computing we can build scalable parallel computers, beyond the current digitaltechnology, under very tight constraints. Of course, this depends on the physical realizationof the inherently nonlinear gate introduced in the paper and thus it is worthwhile exploring itsimplementation. Furthermore, we do not need to limit ourselves to the fundamental linear modelsof systems to obtain useful devices; we should explore systems at a diﬀerent level of abstractionsthat may not be deﬁned by linear equations.This paper is organized as follows: Section 2 summarizes the current model of quantumcomputing, together with the associated problems, including some new issues not discussed in theliterature. Section 3 ﬁrst deﬁnes a framework for new quantum computing models, based on theproblems discussed in Section 2. The
D
gate is introduced within this framework. (This is theonly speculative part of the paper; that is, we do not know how to implement the
D
gate.) QNNsare deﬁned to be Deutsch’s quantum computational network [14] together with the
D
gate.Section 4 quantiﬁes the computational power of the new model. We prove that equalitythreshold circuits have essentially the same computational power as the standard class of thresholdcircuits used for modeling neural networks. Then QNNs are shown to have the same computationalpower as equality threshold gates. Section 5 deﬁnes the precise dynamics of the
D
gate. Section6 identiﬁes some of the many nonlinearities in quantum systems. Finally, Section 7 delineatesmany interesting research directions suggested by this paper.
2 Current Model of Quantum Computing
There are two equivalent models for quantum computing, quantum Turing machines [13, 8] basedon reversible Turing machines [6, 7] and quantum computational network [14]. Our model buildson the latter, so we brieﬂy review it here. The basic unit in quantum computation is a
qubit
,2

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x