Circuit Theory and Computational Models
G ILSON A NTONIO G IRALDI1
1LNCC–National Laboratory for Scientific Computing-
Av.Getulio Vargas,333,25651-070,Petropolis,RJ,Brazil
{gilson}@lncc.br
Abstract.Concepts in Circuit Theory and Computational Paradigms
1Introduction
In this chapter we develop basic elements of another model of computation,the circuit model,which is equivalent to the recursive partial functions(RPF)model in terms of computational power,but is more convenient for many applications.Both models can be used to address the problem of characterizing the set of computable functions.However,sometimes the circuit models is more intuitive then the RPF model.Besides,for some applications the viewpoint of breaking the computation in a graph of gates is much more natural and convenient then functional operations,like composition and recursion.That is the
case of quantum computing[4,6]and neural computation[1]paradigms,which are briefly discussed in sections3.2and3.1,respectively.
In this Chapter,we summarize the basic elements of circuit theory and its application for the men-tioned computational paradigms.Section2will development elements of circuit theory.Then,quantum computing and neural networks are briefly discussed and their relationships with circuit theory pre-sented.The equivalence between RPF and circuit framework is proposed as an exercise(section4).
2Circuit Theory
In this section we start with a practical development found in[4],page129.So,we may say that a circuit is made up wires and gates.The wires carry information around and the gates(functions)perform simple computational tasks.The simplest gates are the logic operators presented on a previous Chapter and the corresponding functions are defined by their truth Tables.The Figure1shows the elementary gates and their graphical representation.Also,we can add to the set of elementary gates the identity(just a wire) and the FANOUT which replace a bit with two copies of itself.
In Figure2it is pictured an example of a circuit that outputs the result of the Boolean expression x⊕y together with a carry bit set to1if x and y are both1,or0otherwise(check it!).
Formally,let G be a set of gates that map several bits to one bit.For each n≥0,a circuit C n over the set G is a directed,acyclic graph with a list of input nodes(with no incoming edges),a list of output nodes(with no outgoing edges),and a gate in G labeling each non-input/non-output node.Given a binary input string(x1,x2,...,x n)∈{0,1}n,we label each input node x i or∼x i(NOT(x i)).For every other node v with m predecessors(y1,y2,...,y n),we recursively assign a value g(y1,y2,...,y n), where g is the gate that labels node v.The circuit C n outputs the value given by the list of output nodes.
The size of a circuit C n is its number of nodes and the depth of C n is the length of the longest path from any input node to an output node.
Figure1:Basic Gates.
Figure2:Circuit example.
A circuit family is a list of circuits C=(C1,C2,...,C n,...)where C i has i binary inputs.The family C computes a family of Boolean functions(f1,f2,...,f n,...),where f i is the boolean function computed by circuit C i.
We say that the family C has size complexity s(n)and depth complexity d(n)if for all n≥0circuit C n has size at most s(n)and depth at most d(n).Size and depth are important complexity descriptions of circuits that respectively characterize the computational resources and the number of steps needed to compute a family of boolean functions.Important classes of circuits are the following ones.
2.1Threshold Circuits
A weighted threshold function of weight bound w and threshold∆∈Z(set of integers)is a boolean function denoted by T n,∆
w1,w2,...,w n
and defined as follows[7]:
T h n,∆
w1,w2,...,w n
:{0,1}n→{0,1},
T h n,∆
w1,w2,...,w n (x1,x2,...,x n)=1,if
n
i=1
spring framework表达式assign
w i x i≥∆,
T h n,∆
w1,w2,...,w n
(x1,x2,...,x n)=0,otherwise,
where(w1,w2,...,w n)∈Z n,|w i|≤w for all i.
If we restricted to the case of w i=1,i=1,2,..,n,we just denote T h n,∆:{0,1}n→{0,1}and call T h n,∆a threshold function with threshold∆.A threshold circuit is a circuit over the set of threshold gates(functions).Let T C(s(n),d(n))denote the collection of threshold circuits of size s(n)and depth d(n).The class of functions that can be computable by these circuits will be denoted as T C.We have analogous definitions for the collection of weighted threshold circuits and the class of functions that are computable by them,denoted by W T C(s(n),d(n))and W T C,respectively.
An important theorem about threshold circuits is the following one:
Theorem:Suppose an analytic function f(x)has a convergent Taylor series expansion f(x)= ∞n=0c n(x−x
0)n over an interval|x−x0|<ε,where0<ε<1,and the coefficients are rational numbers c n=a n/b n,where a n,b n are integers with magnitude at most2n O(1).Then,f(x)can be efficiently computed over this interval,within accuracy2−n c,for any constant c≥1,by threshold circuits of polynomial size and simultaneous constant depth[7].
2.2Equality Threshold Circuits
A weighted equality threshold function of weight bound w≥0is a boolean function defined by:
Et n w
1,...,w n
:{0,1}n→{0,1},
Et n w
1,...,w n (x1,x2,...,x n)=0,if
n
i=1
w i x i=0,
Et n w
1,...,w n
(x1,x2,...,x n)=1,otherwise,
for(w1,w2,...,w n)∈Z n,|w i|≤w for all i.
An equality threshold circuit of weight bound w≥0is a circuit over the set of equality threshold gates such that all the weights are absolutely bounded by w.Let EC(s(n);d(n))denote the collection of equality circuits of size s(n)and depth d(n).EC will also be used to denote the class of functions computable by these circuits.
It is possible to show that the weights of a EC circuit can be encoded appropriately in unitary matrices,and quantum entanglement and interference can be used to compute n i=1w i x i in one step. Thus,EC provide a good model to help in the combination of ideas from quantum computing and threshold circuits[3].
3Circuit Theory and Computational Paradigms
It is important to observe how the theory summarized above helps the development of non usual com-putational paradigms.Specifically,quantum computing and neural computing are two such frameworks for which the theory of circuits are fundamental.Artificial Neural Networks(ANNs)have been stud-ied and applied infields like cognitive science,pattern recognition and classification[1].On the other hand,in the last two decades we observed a growing interest in Quantum Computation and Quantum Information due to the possibility to solve efficiently hard problem for conventional computer science paradigms.Quantum computation and quantum information encompasses processing and transmission of data stored in quantum states(see[5]and references therein).
Recently,several works have been done in artificial neural networks(ANNs)based on quantum theoretical concepts and techniques due to cognitive science and computer science aspects.The so called Quantum Neural Networks(QNNs)is an interesting area of research in thefield of quantum computation and quantum information[2].However,a key question about QNNs is what such an architecture will look like as an implementation on quantum hardware.Unfortunately,up to now,there is no a complete solution for the implementation of QNNs.Next,we show some details of both quantum computing and ANNs to explain the application of circuit theory in thesefields.
3.1Classical Neural Networks
Thefirst logical neuron was developed by W.S.McCulloch and W.A.Pitts in1943[1].It describes the fundamentals functions and structures of a neural cell reporting that a neuron willfire an impulse only if a threshold value is exceeded.
Figure3:McCulloch-Pitts neuron model.
Figure3shows the basic elements of McCulloch-Pitts model:x is the input vector,w are weights input associates,y is output,R is number of elements in input and f is the activation function that
determine the value in output.A simple choice for f is the signal function sgn(.).In this case,if the sum,across all the inputs with its respective weights exceeds the threshold b the output is1else the value of y is−1,that is:
y=sgn(
R
i=1
w i x i−b).(1)
But the McCulloch-Pitts neuron did not have a mechanisms for learning.Based on biological evidences,D.O.Hebb suggested a rule to adapt the weights input,which is interpreted as learning rule for the system[1].This biological inspired procedure can be expressed in the following manner:
w new
i
=w old i+∆w i;∆w i=η(y desired−y)x i,(2) where w new and w old are adapted weights and initials weights respectively,ηis a real parameter to control the rate of learning and y desired is the desired(know)output.This learning rule plus the elements of Figure3is called the perceptron model for a neuron.
Then,the learning typically occurs for example through training,or exposure to a know set of input/output data.The training algorithm iteratively adjusts the connection weights{w i}analogous to synapses in biological nervous.These connection weights store the knowledge necessary to solve specific problems.
3.2Quantum Computation
In practice,the most useful model for quantum computation is the Quantum Computational Network also called Deutsch’s model[3,6].The basic information unit in this model is a qubit[4],which can be considered a superposition of two independent states|0 and|1 ,denoted by|ψ =α0|0 +α1|1 , whereα0,α1are complex numbers such that|α0|2+|α1|2=1.
A composed system with n qubits is described using N=2n independent states obtained through the tensor product of the Hilbert Space associated with each qubit.Thus,the resulting space has a natural basis that can be denoted by:
{|i n−1 ;i j∈{0,1}}.(3) This set can be indexed by|i ;i=0,1,...,N−1.Following the Quantum Mechanics Postulates, the state system|ψ ,in any time t,can be expanded as a superposition of the basis states:
|ψ =N−1
i=0αi|i ;N−1
i=0
|αi|2=1.(4)
Entanglement is another important concept for quantum computation with no classical counterpart. To understand it,a simple example is worthwhile..
Let us suppose that we have a composed system with two qubits.According to the above explana-tion,the resulting Hilbert Space has N=22independent states.
Let the Hilbert Space associated with thefirst qubit(indexed by1)denoted by H1and the Hilbert Space associated with the second qubit(indexed by2)denoted by H2.The computational basis for these spaces are given by:{|0 1,|1 1}and{|0 2,|1 2},respectively.If qubit1is in the state|ψ 1=a10|
0 1+a11|1 1and qubit2in the state|ψ 2=a20|0 2+a21|1 2,then the composed system is in the state:|ψ =|ψ 1⊗|ψ 2,explicitly given by:
a1i a2j|i 1⊗|j 2.(5)
|ψ =
i,j∈{0,1}
Every state that can be represented by a tensor product|ψ 1⊗|ψ 2belongs to the tensor product space H1⊗H2.However,there are some states in H1⊗H2that can not be represented in the form |ψ 1⊗|ψ 2.They are called entangled states.The Bell state(or EPR pair)presented next is a very known example:
|ψ =12(|0 1⊗|0 2+|1 1⊗|1 2).(6) Trying to represent this state as a tensor product|ψ 1⊗|ψ 2,with|ψ 1∈H1and|ψ 2∈H2, produces an inconsistent linear system without solution.
Entangled states are fundamental for teleportation[4].In recent years,there has been tremendous efforts trying to better understand the properties of entanglement,not only as a fundamental resource for the Nature,but also for quantum computation and information.
The computation unit in Deutsch’s model consists of quantum gates which are unitary operators that evolves an initial state performing the necessary computation to get the desired result.A quantum com
puting algorithm can be summarized in three steps:(1)Prepare the initial state;(2)A sequence of (universal)quantum gates to evolve the system;(3)Quantum measurements.
From quantum mechanics theory,the last stage performs a collapse and only what we know in advance is the probability distribution associated to the measurement operation.So,it is possible that the result obtained by measuring the system should be post-processed to achieve the target(quantum factoring(Chapter6of[6])is a nice example).
The most used computational model in quantum computing is the circuit one because itfits very well with the Deutsch’s model.The Figure4shows a representation of a quantum circuit.
Figure4:Example of quantum circuit with generic quantum gates denoted by U and D.
4Exercises
1.Show that any functions f:{0,1}n→{0,1}can be computed by a circuit.
2.Show that the circuit model and the Partial Recursive Functions(PRF)model are equivalent;that is,show that any function f:{0,1}n→{0,1}can be computed by both the PRF and circuit model.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。