门禁高级教程 第九章 功夫在技术之外

Quantum Walks on the HypercubeC RISTOPHER M OOREComputer Science DepartmentUniversity of New Mexico,Albuquerque and the Santa Fe Institute,Santa Fe,New Mexicomoore@A LEXANDER R USSELL Department of Computer Science and Engineering University of ConnecticutStorrs,Connecticutacr@November12,2001AbstractRecently,it has been shown that one-dimensional quantum walks can mix more quickly than clas-sical random walks,suggesting that quantum Monte Carlo algorithms can outperform their classicalcounterparts.We study two quantum walks on the n-dimensional hypercube,one in discrete time andone in continuous time.In both cases we show that the instantaneous mixing time isπ4n steps,fasterthan theΘn log n steps required by the classical walk.In the continuous-time case,the probabilitydistribution is exactly uniform at this time.On the other hand,we show that the average mixing timeas defined by Aharonov et al.[AAKV01]isΩn32in the discrete-time case,slower than the classical walk,and nonexistent in the continuous-time case.This suggests that the instantaneous mixing time is amore relevant notion than the average mixing time for quantum walks on large,well-connected graphs.Our analysis treats interference between terms of different phase more carefully than is necessary for thewalk on the cycle;previous general bounds predict an exponential average mixing time when applied tothe hypercube.1IntroductionRandom walks form one of the cornerstones of theoretical computer science.As algorithmic tools,theyhave been applied to a variety of central problems,such as estimating the volume of a convex body[DFK91,LK99],approximating the permanent[JS89,JSV00],andfinding satisfying assignments for Boolean for-mulae[Sch99].Furthermore,the basic technical phenomena appearing in the study of random walks(e.g.,spectral decomposition,couplings,and Fourier analysis)also support several other important areas such aspseudorandomness and derandomization(see,e.g.,[AS92,(9,15)]).The development of efficient quantum algorithms for problems believed to be intractable for classicalrandomized computation,like integer factoring and discrete logarithm[Sho97],has prompted the investi-gation of quantum walks.This is a natural generalization of the traditional notion discussed above where,roughly,the process evolves in a unitary rather than stochastic fashion.The notion of“mixing time,”thefirst time when the distribution induced by a random walk is sufficientlyclose to the stationary distribution,plays a central role in the theory of classical random walks.For a givengraph,then,it is natural to ask if a quantum walk can mix more quickly than its classical counterpart.(Sincea unitary process cannot be mixing,we define a stochastic process from a quantum one by performinga measurement at a given time or a distribution of times.)Several recent articles[AAKV01,ABN01,NV00]have answered this question in the affirmative,showing,for example,that a quantum walk on then-cycle mixes in time O n log n,a substantial improvement over the classical random walk which requires Θn2steps to mix.Quantum walks were also defined in[Wat01],and used to show that undirected graph connectivity is contained in a version of quantum LOGSPACE.These articles raise the exciting possibilitythat quantum Monte Carlo algorithms could form a new family of quantum algorithms that work morequickly than their classical counterparts.Two types of quantum walks exist in the literature.Thefirst,introduced by[AAKV01,ABN01,NV00],studies the behavior of a“directed particle”on the graph;we refer to these as discrete-time quantumwalks.The second,introduced in[FG98,CFG01],defines the dynamics by treating the adjacency matrixof the graph as a Hamiltonian;we refer to these as continuous-time quantum walks.The landscape isfurther complicated by the existence of two distinct notions of mixing time.The“instantaneous”notion[ABN01,NV00]focuses on particular times at which measurement induces a desired distribution,whilethe“average”notion[AAKV01],another natural way to convert a quantum process into a stochastic one,focuses on measurement times selected randomly from some interval.In this article,we analyze both the continuous-time and a discrete-time quantum walk on the hypercube.In both cases,the walk is shown to have an instantaneous mixing time atπ4n.(Of course,in the discretewalk all times are integers.)Recall that the classical walk on the hypercube mixes in timeΘn log n,sothat the quantum walk is faster by a logarithmic factor.Moreover,in the discrete-time case the walk mixesin time less than the diameter of the graph,sinceπ41;astonishingly,in the continuous-time case theprobability distribution at tπ4n is exactly uniform.Both of these things happen due to a marvelousconspiracy of destructive interference between terms of different phase.These walks show i.)a similarity between the two notions of quantum walks,and ii.)a disparity between the two notions of quantum mixing times.As mentioned above,both walks have an instantaneous mixing time at timeπ4n.On the other hand,we show that the average mixing time of the discrete-time walk isΩn32,slower than the classical walk,and that for the continuous-time walk there is no time at which the time-averaged probability distribution is close to uniform in the sense of[AAKV01].Our results suggest that for large graphs(large compared to their mixing time)the instantaneous notion of mixing time is more appropriate than the average one,since the probability distribution is close to uniform only in a narrow window of time.The analysis of the hypercubic quantum walk exhibits a number of features markedly different fromthose appearing in previously studied walks.In particular,the dimension of the relevant Hilbert space is,for the hypercube,exponential in the length of the desired walk,while in the cycle these quantities are roughly equal.This requires that interference be handled in a more delicate way than is required for the walk on the cycle;in particular,the general bound of[AAKV01]yields an exponential upper bound on the mixing time for the discrete-time walk.We begin by defining quantum walks and discussing various notions of mixing time.We then analyze the two quantum walks on the hypercube in Sections2and3.(Most of the technical details for the discrete-time walk are relegated to an appendix.)1.1Quantum walks and mixing timesAny graph G V E gives rise to a familiar Markov chain by assigning probability1d to all edges leaving each vertex v of degree d.Let P t u v be the probability of visiting a vertex v at step t of the random walk on G starting at u.If G is undirected,connected,and not bipartite,then lim t∞P t u exists1and is independent of u.A variety of well-developed techniques exist for establishing bounds on the rate at which P t u achieves this limit(e.g.,[Vaz92]);if G happens to be the Cayley graph of a group(as are,for example,the cycle and the hypercube),then techniques from Fourier analysis can be applied[Dia88].Below we will use some aspects of this approach,especially the Diaconis-Shahshahani bound on the total variation distance[DS81].For simplicity,we restrict our discussion to quantum walks on Cayley graphs;more general treatments of quantum walks appear in[AAKV01,FG98].Before describing the quantum walk models we set down some notation.For a group G and a set of generatorsΓsuch thatΓΓ1,let X GΓdenote the undirected Cayley graph of G with respect toΓ.For a finite set S,we let L S f:S denote the collection of-valued functions on S with∑s S f s2 1. This is a Hilbert space under the natural inner product f g∑s S f s g s.For a Hilbert space V,a linear operator U:V V is unitary if for all v w V,v w U v U w;if U is represented as a matrix,this is equivalent to the condition that U†U1where†denotes the Hermitian conjugate.There are two natural quantum walks that one can define for such graphs,which we now describe.T HE DISCRETE-TIME WALK:This model,introduced by[AAKV01,ABN01,NV00],augments the graph with a direction space,each basis vector of which corresponds one of the generators inΓ.A step of the walk then consists of the composition of two unitary transformations;a shift operator which leaves the direction unchanged while moving the particle in its current direction,and a local transformation which op-erates on the direction while leaving the position unchanged.To be precise,the quantum walk on X GΓis defined on the space L GΓL G LΓ.LetδγγΓbe the natural basis for LΓ,andδg g G the natural basis for L G.Then the shift operator is S:δgδγδgγδγ,and the local transformation isˇD1D where D is defined on LΓalone and1is the identity on L G.Then one“step”of the walk corresponds to the operator UˇDV.If we measure the position of the particle,but not its direction,at time t,we observe a vertex v with probability P t v∑γΓU tψ0δvδγ2whereψ0L GΓis the initial state.T HE CONTINUOUS-TIME WALK:This model,introduced in[FG98],works directly on L G.The walk evolves by treating the adjacency matrix of the graph as a Hamiltonian and using the Schr¨o dinger equation. Specifically,if H is the adjacency matrix of X GΓ,the evolution of the system at time t is given by U t, where U t eq e iHt(here we use the matrix exponential,and U t is unitary since H is real and symmetric). Then if we measure the position of the particle at time t,we observe a vertex v with probability P t vU tψ0δv2whereψ0is the initial state.Note the analogy to classical Poisson processes:since U t e iHt 1In fact,this limit exists under more general circumstances;see e.g.[MR95].1iHt iHt22,the amplitude of making s steps is the coefficient it s s!of H s,which up to normalization is Poisson-distributed with mean t.Remark.In[CFG01],the authors point out that defining quantum walks in continuous time allows unitarity without having to extend the graph with a direction space and a chosen local operation.On the other hand,it is harder to see how to carry out such a walk in a generically programmable way using only local information about the graph,for instance in a model where we query a graph tofind out who our neighbors are.Instead,continuous-time walks might correspond to special-purpose analog computers,where we build in interactions corresponding to the desired Hamiltonian and allow the system to evolve in continuous time.In both cases we start with an initial wave function concentrated at a single vertex corresponding to the identity u of the group.For the continuous-time walk,this corresponds to a wave functionψ0v ψ0δv(so thatψ0u1andψ0v0for all v u).For the discrete-time walk,we start with a uniform superposition over all possible directions,ψ0vγψ0δvδγ1Γif v u 0otherwise.For the hypercube,u000.In order to define a discrete-time quantum walk,one must select a local operator D on the directionspace.In principle,this introduces some arbitrariness into the definition.However,if we wish D to respectthe permutation symmetry of the n-cube,and if we wish to maximize the operator distance between D andthe identity,we show in Appendix A that we are forced to choose Grover’s diffusion operator[Gro96],which we recall below.We call the resulting walk the“symmetric discrete-time quantum walk”on then-cube.(Watrous[Wat01]also used Grover’s operator to define quantum walks on undirected graphs.)Since for large n Grover’s operator is close to the identity matrix,one might imagine that it would takeΩn12steps to even change direction,giving the quantum walk a mixing time of n32,slower than the classical random walk.However,like many intuitions about quantum mechanics,this is simply wrong.Since the evolution of the quantum walk is governed by a unitary operator rather than a stochastic one,unless P t is constant for all t,there can be no“stationary distribution”lim t∞P t.In particular,for anyε0,there are infinitely many(positive,integer)times t for which U t1εso that U tψuψuεand P t is close to the initial distribution.However,there may be particular stopping times t which induce distributions close to,say,the uniform distribution,and we call these instantaneous mixing times:Definition1We say that t is anε-instantaneous mixing time for a quantum walk if P t Uε,where A B12∑v A v B v denotes total variation distance and U denotes the uniform distribution.For these walks we show:Theorem1For the symmetric discrete-time quantum walk on the n-cube,t kπ4n is anε-instantaneousmixing time withεO n76for all odd k.and,even more surprisingly,Theorem2For the continuous-time quantum walk on the n-cube,t kπ4n is a0-instantaneous mixingtime for all odd k.Thus in both cases the mixing time isΘn,as opposed toΘn log n as it is in the classical case.Aharonov et al.[AAKV01]define another natural notion of mixing time for quantum walks,in whichthe stopping time t is selected uniformly from the set0T1.They show that the time-averageddistributions¯P T1T∑T1t0P t do converge as T∞and study the rate at which this occurs.For a continuous-time random walk,we analogously define the distribution¯P T v1T T0P t v d t.Then we call a time at which¯P T is close to uniform an average mixing time:Definition2We say that T is anε-average mixing time for a quantum walk if¯P T Uε.In this paper we also calculate theε-average mixing times for the hypercube.For the discrete-time walk,it is even longer than the mixing time of the classical random walk:Theorem3For the discrete-time quantum walk on the n-cube,theε-average mixing time isΩn32ε. This is surprising given that the instantaneous mixing time is only linear in n.However,the probability distribution is close to uniform only in narrow windows around the odd multiples ofπ4n,so¯P T is far from uniform for significantly longer times.We also observe that the general bound given in[AAKV01]yields an exponential upper bound on the average mixing time,showing that it is necessary to handle interference for walks on the hypercube more carefully than for those on the cycle.For the continuous-time walk the situation is even worse:while it possesses0-instantaneous mixing times at all odd multiples ofπ4n,the limiting distribution lim T∞¯P T is not uniform,and we show the following:Theorem4For the continuous-time quantum walk on the n-cube,there existsε0such that no time is an ε-average mixing time.Our results suggest that in both the discrete and continuous-time case,the instantaneous mixing time is a more relevant notion than the average mixing time for large,well-connected graphs.2The symmetric discrete-time walkIn this section we prove Theorem1.We treat the n-cube as the Cayley graph of n2with the regular basis vectors e i010with the1appearing in the i th place.Then the discrete-time walk takes place in the Hilbert space L n2n where n1n.Here thefirst component represents the position x of the particle in the hypercube,and the second component represents the particle’s current“direction”;if this is i,the shift operator willflip the i th bit of x.As in[AAKV01,NV00],we will not impose a group structure on the direction space,and will Fourier transform only over the position space.For this reason,we will express the wave functionψL n2n as a functionΨ:n2n,where the i th coordinate ofΨx is the projection ofψintoδxδi,i.e.the complex amplitude of the particle being at position x with direction i.The Fourier transform of such an elementΨis˜Ψ:n2n,where˜Ψk∑x1k xΨx.Then the shift operator for the hypercube is S:Ψx∑n i1πiΨx e i where e i is the i th basis vector in the n-cube,andπi is the projection operator for the i th direction.The reason for considering the Fourier transform above is that the shift operator isdiagonal in the Fourier basis:specifically it maps˜Ψk Sk˜Ψk whereS k 1k101k2...01k nFor the local transformation,we use Grover’s diffusion operator on n states,D i j2nδi j.The advantage of Grover’s operator is that,like the n-cube itself,it is permutation symmetric.We use thissymmetry to rearrange UkSkD to put the negated rows on the bottom,UkSkD2n12n2n2n12n......2n12n2n2n2n1......where the top and bottom blocks have n k and k rows respectively;here k is the Hamming weight of k.The eigenvalues of Uk then depend only on k.Specifically,Ukhas the eigenvalues1and1withmultiplicity k1and n k1respectively,plus the eigenvaluesλλwhereλ12kn2ink n k e iωkandωk0πis described bycosωk12knsinωk2nk n kIts eigenvectors with eigenvalue1span the k1-dimensional subspace consisting of vectors with support on the k“flipped”directions that sum to zero,and similarly the eigenvectors with eigenvalue1span the n k1-dimensional subspace of vectors on the n k other directions that sum to zero.We call these the trivial eigenvectors.The eigenvectors ofλλe iωk arev k v k1in k 1 kWe call these the non-trivial eigenvectors for a given k.Over the space of positions and directions these eigenvectors are multiplied by the Fourier coefficient1k x,so as a function of x and direction1j n the two non-trivial eigenstates of the entire system,for a given k,arev k x j1k x2n21if kj1i n k if k j0with eigenvalue e iωk,and its conjugate vkwith eigenvalue e iωk.We take for our initial wave function a particle at the origin000in an equal superposition of directions.Since its position is aδ-function in real space it is uniform in Fourier space as well as over thedirection space,giving˜Ψ0k2n2n 11This is perpendicular to all the trivial eigenvectors,so theiramplitudes are all zero.The amplitude of its component along the non-trivial eigenvector vkisa k Ψ0vk2n2kni1kn(1)and the amplitude of vk is ak.Note that ak22n2,so a particle is equally likely to appear in eithernon-trivial eigenstate with any given wave vector.At this point,we note that there are an exponential number of eigenvectors in which the initial state has a non-zero amplitude.In Section2.1,we observe that for this reason the general bound of Aharonov et al. [AAKV01]yields an exponential(upper)bound on the mixing time.In general,this bound performs poorly whenever the number of important eigenvalues is greater than the mixing time.Instead,we will use the Diaconis-Shahshahani bound on the total variation distance in terms of the Fourier coefficients of the probability[Dia88].If P t x is the probability of the particle being observed at position x at time t,and U is the uniform distribution,then the total variation distance is bounded byP t U214∑k00k11˜Pt k214n1∑k1nk˜Pt k2(2)Here we exclude both the constant term and the parity term k 11;since our walk changes position at every step,we only visit vertices with odd or even parity at odd or even times respectively.Thus U here means the uniform distribution with probability 2n 1on the vertices of appropriate parity.To find ˜Pt k ,we first need ˜Ψt k .As Nayak and Vishwanath [NV00]did for the walk on the line,we start by calculating the t th matrix power of U k .This isU t k a 1t aa a1t c ......b 1t bc bb 1t ......wherea cos ωk t 1t n k b cos ωk t 1t k and c sin ωk t Starting with the uniform initial state,the wave function after t steps is˜Ψt k 2n 2n cos ωk t n k sin ωk t n kcos ωk t n kksin ωk t k (3)In the next two sections we will use this diagonalization to calculate the average and instantaneous mixing times,which are Ωn 32and Θn respectively.2.1Bounds on the average mixing time of the discrete-time walkIn this section,we prove Theorem 3.To do this,it’s sufficient to calculate the amplitude at the origin.Fouriertransforming Equation 3back to real space at x 00gives ψt 02n 2∑k ˜Ψt k 2n n n ∑k 0n k cos ωk t cos ωk tnThe probability the particle is observed at the origin after t steps is thenP t 0ψt 022nn ∑k 0n k cos ωk t 2Let k 1x n 2.For small x ,k is near the peak of the binomial distribution,and ωk cos 1x π2x O x 3so the angle θbetween ωk for successive values of k is roughly constant,θ2n O x 2leading to constructive interference if θt 2π.Specifically,let t m be the even integer closest to πmn forinteger m .Then cos ωk t mcos 2πkm O x 3mn 1O x 6m 2n 2.By a standard Chernoff bound,2n ∑k 1x n 2n k o 1so long as x ωn 12.Let x νn n 12where νn is a function that goes to infinity slowly as a function of n .We then write P t 0o 12n1x n 2∑k 1x n 2n k 1O x 6m 2n 221O νn 6m 2nwhich is 1o 1as long as m o n 12νn 3,in which case t mo n 32νn 3.For a functionψ:n2n withψ21and a set S n2,we say thatψis c-supported on S if the probability x S is at least c,i.e.∑x S d nψx d2c.The discussion above shows thatψt m is 1o1-supported on0for appropriate t mπmn.Note that ifψis c-supported on0then,as U is local,U kψmust be c1c2c1-supported on W k,the set of vertices of weight k.(The factor of1c is due to potential cancellation with portions of the wave function supported outside0.)Inparticular,at times t m k,for k n2n,ψt m k is1o1-supported on W n2x.If x x nωn,then W12δn2n o1and,evidently,the average1T∑T i P i has total variation distance1o1from the uniform distribution if T o n32.Thus we see that in the sense of[AAKV01],the discrete-time quantum walk is actually slower than the classical walk.In the next section,however,we show that its instantaneous mixing time is only linear in n.We now observe that the general bound of[AAKV01]predicts an average mixing time for the n-cube which is exponential in n.In that article it is shown that the variation distance between¯P T and the uniform distribution(or more generally,the limiting distribution lim T∞¯P T)is bounded by a sum over distinct pairs of eigenvalues,¯PT U 2T∑i j s tλiλja i2λiλj(4)where a iψ0v i is the component of the initial state along the eigenvector v i.(Since this bound includes eigenvaluesλj for which a j0,we note that it also holds when we replace a i2with a i a j,using the same reasoning as in[AAKV01].)For the quantum walk on the cycle of length n,this bound gives an average mixing time of O n log n. For the n-cube,however,there are exponentially many pairs of eigenvectors with distinct eigenvalues,all ofwhich have a non-zero component in the initial state.Specifically,for each Hamming weight k there are nk non-trivial eigenvectors each with eigenvalue e iωk and e iωk.These complex conjugates are distinct from each other for0k n,and eigenvalues with distinct k are also distinct.The number of distinct pairs is thenn1∑k1nk24n∑k k0nknkΩ4nTaking a k2n2from Equation1and the fact thatλiλj2since theλi are on the unit circle, we see that Equation4gives an upper bound on theε-average mixing time of sizeΩ2nε.In general,this bound will give a mixing time of O Mεwhenever the initial state is distributed roughly equally over M eigenvectors,and when these are roughly equally distributed overω1distinct eigenvalues.2.2The instantaneous mixing time of the discrete-time walkTo prove Theorem1we could calculateΨt x by Fourier transforming˜P t k back to real space for all x. However,this calculation turns out to be significantly more awkward than calculating the Fourier trans-form of the probability distribution,˜P t k,which we need to apply the Diaconis-Shahshahani bound.Since P t xΨt xΨt x,and since multiplications in real space are convolutions in Fourier space,we perform a convolution over n2:˜Pt k∑k ˜Ψt k˜Ψt k kwhere the inner product is defined on the direction space,u v∑n i1u i v i.We write this as a sum over j, the number of bits of overlap between k and k,and l,the number of bits of k outside the bits of k(and so overlapping with k k).Thus k has weight j l,and k k has weight k j l.Calculating the dot product˜Ψt k˜Ψt k k explicitly from Equation3as a function of these weights and overlaps gives˜P t k 12k∑j0n k∑l0kjn klcosωj l t cosωk j l t A sinωj l t sinωk j l t(5)whereA cosωk cosωj l cosωk j l sinωj l sinωk j lThe reader can check that this gives˜P t01for the trivial Fourier component where k0,and˜P t n 1t for the parity term where k n.Using the identities cos a cos b12cos a b cos a b and sin a sin b12cos a b cos a b we can re-write Equation5as˜P t k 12k∑j0n k∑l0kjn kl1A2cosωt1A2cosωt12k∑j0n k∑l0kjn klY(6)whereωωj lωk j l.The terms cosωt in Y are rapidly oscillating with a frequency that increases with t.Thus,unlike the walk on the cycle,the phase is rapidly oscillating everywhere,as a function of either l or j.This will make the dominant contribution to˜P t k exponentially small when t nπ4,giving us a small variation distance when we sum over all k.To give some intuition for the remainder of the proof,we pause here to note that if Equation6were an integral rather than a sum,we could immediately approximate the rate of oscillation of Y tofirst order at the peaks of the binomials,where j k2and l n k 2.One can check that dωk d k2n and hence dωd l dωd j4n.Since A1,we would then write˜Pt k O 12k∑j0n k∑l0kjn kle4i jt n e4ilt nwhich,using the binomial theorem,would give˜Pt k O 1e4it n2k1e4it n2n kcos k2tncos n k2tn(7)In this case the Diaconis-Shahshahani bound and the binomial theorem giveP t U214∑0k nnkcos k2tncos n k2tn2122cos22tnn1cos22tnn1If we could take t to be the non-integer valueπ4n,these cosines would be zero.This will,in fact,turn out to be the right answer.But since Equation6is a sum,not an integral,we have to be wary of resonances where the oscillations are such that the phase changes by a multiple of2πbetween adjacent terms,in which case these terms will interfere constructively rather than destructively.Thus to show that thefirst-order oscillation indeed dominates,we have a significant amount of work left to do.The details of managing these resonances can be found in Appendix B.The process can be summarized as follows:i.)we compute the Fourier transform of the quantity Y in Equation6,since the sum of Equation6 can be calculated for a single Fourier basis function using the binomial theorem;ii.)the Fourier transform0.20.40.60.810.20.40.60.81(a)Variation distance at time t as a function of t n .(b)Log 2Probability as a function of Hamming weight.Figure 1:Graph (a)plots an exact calculation of the total variation distance after t steps of the quantum walk for hypercubes of dimension 50,100,and 200,as a function of t n .At t n π4the variation distance is small even though the walk has not had time to cross the entire graph.This happens because the distribution is roughly uniform across the equator of the n -cube where the vast majority of the points are located.Note that the window in which the variation distance is small gets narrower as n increases.Graph (b)shows the log 2probability distribution on the 200-dimensional hypercube as a function of Hamming distance from the starting point after 157π4n steps.The probability distribution has a plateau of 2199at the equator,matching the uniform distribution up to parity.of Y can be asymptotically bounded by the method of stationary phase.The dominant stationary point corresponds to the first-order oscillation,but there are also lower-order stationary points corresponding to faster oscillations;so iii.)we use an entropy bound to show that the contribution of the other stationary points is exponentially small.To illustrate our result,we have calculated the probability distribution,and the total variation distance from the uniform distribution (up to parity),as a function of time for hypercubes of dimension 50,100,and 200.In order to do this exactly,we use the walk’s permutation symmetry to collapse its dynamics to a function only of Hamming distance.In Figure 1(a)we see that the total variation distance becomes small when t n π4,and in Figure 1(b)we see how the probability distribution is close to uniform on a “plateau”across the hypercube’s equator.Since this is where the vast majority of the points are located,the total variation distance is small even though the walk has not yet had time to cross the entire graph.3The continuous-time walkIn the case of the hypercube,the continuous-time walk turns out to be particularly easy to analyze.Theadjacency matrix,normalized by the degree,is H x y1n if x and y are adjacent,and 0otherwise.Interpreting H as the Hamiltonian treats it as the energy operator,and of course increasing the energy makes the system run faster;we normalize by the degree n in order to keep the maximum energy of the system,and so the rate at which transitions occur,constant as a function of n .The eigenvectors of H and U t are simply the Fourier basis functions:if v k x1k x then Hv k 12k n v k and U t v k e it 12k n v k where we again use k to denote the Hamming weight of k .If our initial wave vector has a particle at 0,then its initial Fourier spectrum is uniform,and at time t we have˜Ψt k 2n 2e it 12k n Again writing the probability P as the convolution of Ψwith Ψin Fourier space,。

NICE900默纳克门机使用说明一、产品简介二、安装前准备1.确定门机的安装位置，并确保该位置离电源和控制设备近，并且没有障碍物。

2.确保门机的安装台面平直，稳固。

3.准备好所需的安装工具和材料：电钻、扳手、螺丝刀、膨胀螺丝、电线等。

三、安装步骤1.固定安装台面：使用膨胀螺丝将安装台面固定在安装位置上。

2.安装传动装置：根据传动装置的指引，将其安装在门机的适当位置上，并用螺丝固定好。

3.安装门机上部组件：根据门机的具体型号，将上部组件（如开关按钮、传感器等）按照说明书上的指引安装好。

4.安装门机下部组件：根据门机的具体型号，将下部组件（如地感器、警告灯等）按照说明书上的指引安装好。

5.连接电线：根据电气控制箱上的接线图，将电线正确连接到门机和控制设备上。

6.调试门机：接通电源后，按照说明书上的指引进行门机的调试和测试，确保其正常运行。

四、使用方法1.开门操作：门机配备有开门按钮，按下按钮后门会自动打开。

也可以通过无线遥控器、密码输入等方式进行开门操作。

2.关门操作：门机设置了自动关门功能，一段时间内无人通过后门会自动关闭。

也可以通过关闭按钮或无线遥控器手动关闭门。

3.警告功能：门机配备了警告灯和警报器，在门机工作异常或有障碍物等情况下会启动警告功能。

当警告灯亮起或警报器响起时，请及时检查门机。

五、注意事项1.请确保门机的安装牢固可靠，避免因门机脱落或松动而导致意外事故。

2.在使用过程中，请勿将手指等物体伸入门机运动区域，以防意外夹伤。

3.请定期对门机进行维护保养，确保其正常运行。

5.请勿随意更改门机的工作参数和电路连接，以免影响正常使用和安全性能。

六、维护保养1.定期清洁门机及其组件，确保其正常运行。

2.检查门机螺丝和连接部位是否松动，如有松动请及时固定好。

3.保持门机电源供应正常，注意防止漏电和电源过载。

4.定期检查门机电控系统的各个连接部位，确保其接触良好。

5.定期检查门机的传动装置和传感器，保持其灵敏度和稳定性。

智能化门禁系统设计方案智能化门禁系统设计方案随着社会的不断发展，人们对于安全问题的关注度也越来越高，特别是对于居住和工作地点的安全问题。

因此，门禁系统的需求也在不断增加。

智能化门禁系统，作为门禁系统的一种重要发展方向，其应用范围越来越广泛。

为了能够满足人们不断提高的门禁系统需求，我们需要对智能化门禁系统进行设计，以提供更加全面和高效的门禁解决方案。

本文将探讨智能化门禁系统的设计方案。

设计目标首先，我们需要明确智能化门禁系统的设计目标。

智能化门禁系统的设计目标可分为以下几点：1.安全性：智能化门禁系统设计必须优先考虑安全问题，确保门禁系统的安全性。

智能化门禁系统需要有完整的数据加密和解密机制来保护对门禁系统的入侵，为保密和敏感信息提供保护。

2.方便性：智能化门禁系统设计必须考虑门禁的使用方便性。

门禁系统的操作必须简单明了，易于操作。

门禁系统必须提供安全可靠的身份验证方式，使用户能够在不受干扰的情况下使用门禁系统。

3.实用性：智能化门禁系统设计必须注重实用性，保证门禁系统的可靠性和持久性。

该系统必须能够适应各种气候条件和环境，提供更高的稳定性和耐用性。

4.易于维护性：智能化门禁系统设计必须考虑门禁系统的易维护性。

门禁系统必须能够快速维修和更换设备，以保证系统的可持续性。

设计要素基于以上目标，我们需要关注以下设计要素：1.身份验证方式：门禁系统的身份验证方式可以是指纹识别、密码识别、人脸识别等。

其中，指纹识别是目前常用的身份验证方式之一。

但是，指纹识别的准确度依赖于人的指纹质量，导致准确度相对较低。

相比之下，人脸识别技术更为先进，能够对人脸图像进行高精度的识别。

因此，对于智能化门禁系统的设计，我们可以考虑采用人脸识别技术作为主要身份识别方式。

2.门禁设备：门禁系统的设备必须追求高品质和高可靠性，包括门禁控制器、门禁读卡器、门禁闸机等。

此外，在设计门禁设备时，还需要考虑设备的外观设计和材质，以保证门禁设备的质量和稳定性。

单门门禁控制器说明书目录一、功能简介 ............................................................ １二、性能参数 ............................................................ １三、接线定义 ............................................................ ２3.1接线表................................................................ ２3.2红外及门磁检测接线原理图.............................................. ４3.3OC门报警输出原理图 ................................................... ４3.4防拆输出端原理图...................................................... ４3.5门铃接线原理图........................................................ ５3.6门禁控制器与读卡器联网示意图.......................................... ５四、操作步骤 ............................................................ ５4.1连接线................................................................ ５4.2刷卡.................................................................. ６4.3加卡.................................................................. ６4.4删卡.................................................................. ６4.5布防按钮.............................................................. ６4.6密码开门.............................................................. ７4.7设置（更换）密码...................................................... ７4.8设置（更换）加卡/删卡设置卡........................................... ７4.9手动开门.............................................................. ７4.10外接读卡头........................................................... ７五、安装说明 ............................................................ ７5.1安装工具及材料准备.................................................... ８5.2安装步骤.............................................................. ８六．接线注意事项 ........................................................ ９七、包装清单 ............................................................ ９一、功能简介该门禁控制器属于专用设备与601MC 读卡器进行对接工作。

•一控制参数SYSTEM
OCSS
GROUP
DRIVE
DOORS
POS.REF
SERVICE（预留）
EMERG
SECURITY
TEST
TIME
REI
Speech（预留）
Remote（预留）
Factory
Position Indicator M-1-3-4
ALLOW CUDE M-1-3-2 Enable Masks
•二驱动参数MONITOR
EVENT LOG
SETUP
LEARN RUN
TEST
Factory
•三控制故障
说明：
1 对于计算次数的故障，次数在快车运行之前或15分钟之内都是累加的，当门区故障时，会判断累计的次数，若累计次数已经>=3次，则保护；当非门区故障时，会判断此时累加的次数，若累加次数已经>=5次，则保护。

2 关于故障次数累加
故障次数累加包含所有累计次数保护的故障，而不是只是针对某个故障。

如发生某个故障时有其他累计次数保护的故障发生，则故障次数也会累加。

3 关于故障次数清零条件
(1)保护之前，快车运行一次之后，累计的故障次数清零
(2)保护之前，15分钟之后，故障次数自动清零(包括控制故障和驱动故障)。