ON THE COMPLEXITY OF COMPUTING DETERMINANTS (Extended abstract)

ON THE COMPUTATIONALCOMPLEXITY OF ALGORITHMSBYJ. HARTMANIS AND R. E. STEARNSI. Introduction. In his celebrated paper [1], A. M. Turing investigated the computability of sequences (functions) by mechanical procedures and showed that the setofsequencescanbe partitioned into computable and noncomputable sequences. One finds, however, that some computable sequences are very easy to compute whereas other computable sequences seem to have an inherent complexity that makes them difficult to compute. In this paper, we investigate a scheme of classifying sequences according to how hard they are to compute. This scheme puts a rich structure on the computable sequences and a variety of theorems are established. Furthermore, this scheme can be generalized to classify numbers, functions, or recognition problems according to their compu-tational complexity.The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. This particular abstract model of a computing device is chosen because much of the work in this area is stimulated by the rapidly growing importance of computation through the use of digital computers, and all digital computers in a slightly idealized form belong to the class of multitape Turing machines. More specifically, if Tin) is a computable, monotone increasing function of positive integers into positive integers and if a is a (binary) sequence, then we say that a is in complexity class ST or that a is T-computable if and only if there is a multitape Turing machine 3~ such that 3~ computes the nth term of a. within Tin) operations. Each set ST is recursively enumerable and so no class ST contains all computable sequences. On the other hand, every computable a is contained in some com-plexity class ST. Thus a hierarchy of complexity classes is assured. Furthermore, the classes are independent of time scale or of the speed of the components from which the machines could be built, as there is a "speed-up" theorem which states that ST = SkT f or positive numbers k.As corollaries to the speed-up theorem, there are several limit conditions which establish containment between two complexity classes. This is contrasted later with the theorem which gives a limit condition for noncontainment. One form of this result states that if (with minor restrictions)Received by the editors April 2, 1963 and, in revised form, August 30, 1963.285286J. HARTMANIS AND R. E. STEARNS[May»*«, U(n)then S,; properly contains ST. The intersection of two classes is again a class. The general containment problem, however, is recursively unsolvable.One section is devoted to an investigation as to how a change in the abstract machine model might affect the complexity classes. Some of these are related by a "square law," including the one-tape-multitape relationship: that is if a is T-computable by a multitape Turing machine, then it is T2-computable by a single tape Turing machine. It is gratifying, however, that some of the more obvious variations do not change the classes.The complexity of rational, algebraic, and transcendental numbers is studied in another section. There seems to be a good agreement with our intuitive notions, but there are several questions still to be settled.There is a section in which generalizations to recognition problems and functions are discussed. This section also provides the first explicit "impossibility" proof, by describing a language whose "words" cannot be recognized in real-time [T(n) = n] .The final section is devoted to open questions and problem areas. It is our conviction that numbers and functions have an intrinsic computational nature according to which they can be classified, as shown in this paper, and that there is a good opportunity here for further research.For background information about Turing machines, computability and related topics, the reader should consult [2]. "Real-time" computations (i.e., T(n) = n) were first defined and studied in [3]. Other ways of classifying the complexity of a computation have been studied in [4] and [5], where the complexity is defined in terms of the amount of tape used.II. Time limited computations. In this section, we define our version of a multitape Turing machine, define our complexity classes with respect to this type of machine, and then work out some fundamental properties of these classes.First, we give an English description of our machine (Figure 1) since one must have a firm picture of the device in order to follow our paper. We imagine a computing device that has a finite automaton as a control unit. Attached to this control unit is a fixed number of tapes which are linear, unbounded at both ends, and ruled into an infinite sequence of squares. The control unit has one reading head assigned to each tape, and each head rests on a single square of the assigned tape. There are a finite number of distinct symbols which can appear on the tape squares. Each combination of symbols under the reading heads together with the state of the control unit determines a unique machine operation. A machine operation consists of overprinting a symbol on each tape square under the heads, shifting the tapes independently either one square left, one square1965]ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMS287ti 1111 i n cm U I I i I I I ID mm.Tn T| in i i i i i i i m-m Î2II I I I I I I I I m II I I I I I I IIP TnTAPESFINITE STATECOMPUTEROUTPUT TAPEFigure 1. An «-tape Turing machineright, or no squares, and then changing the state of the control unit. The machine is then ready to perform its next operation as determined by the tapes and control state. The machine operation is our basic unit of time. One tape is signaled out and called the output tape. The motion of this tape is restricted to one way move-ment, it moves either one or no squares right. What is printed on the output tape and moved from under the head is therefore irrevocable, and is divorced from further calculations.As Turing defined his machine, it had one tape and if someone put k successive ones on the tape and started the machine, it would print some f(k) ones on the tape and stop. Our machine is expected to print successively /(l),/(2), ••• on its output tape. Turing showed that such innovations as adding tapes or tape symbols does not increase the set of functions that can be computed by machines. Since the techniques for establishing such equivalences are common knowledge, we take it as obvious that the functions computable by Turing's model are the same as those computable by our version of a Turing machine. The reason we have chosen this particular model is that it closely resembles the operation of a present day computer; and being interested in how fast a machine can compute, the extra tapes make a difference.To clear up any misconceptions about our model, we now give a formal definition.Definition 1. An n-tape Turing machine, &~, is a set of (3n + 4)-tuples, {(q¡; Stl, Sh, — , Sin ; Sjo, Sjl, — , Sh ; m0, mx, —, m… ; qf)},where each component can take on a finite set of values, and such that for every possible combination of the first n + 1 entries, there exists a unique (3zi-t-4)-tupIe in this set. The first entry, q¡, designates the present state; the next n entries, S(l,-",S,B, designate the present symbols scanned on tapes Tx, •■•, T…,respectively; the next n + 1 symbols SJa, ••-, Sjn, designate the new symbols to be printed on288J. HARTMANIS AND R. E. STEARNS[May tapes T0, •■», T…, respectively; the next n entries describe the tape motions (left, right, no move) of the n + 1 tapes with the restriction m0 # left ; and the last entry gives the new internal state. Tape T0 is called the output tape. One tuple with S¡. = blank symbol for 1 = j = n is designated as starting symbol.Note that we are not counting the output tape when we figure n. Thus a zero-tape machine is a finite automaton whose outputs are written on a tape. We assume without loss of generality that our machine starts with blank tapes.For brevity and clarity, our proofs will usually appeal to the English description and will technically be only sketches of proofs. Indeed, we will not even give a formal definition of a machine operation. A formal definition of this concept can be found in [2].For the sake of simplicity, we shall talk about binary sequences, the general-ization being obvious. We use the notation a = axa2 ••• .Definition 2. Let Tin) be a computable function from integers into integers such that Tin) ^ Tin + 1) and, for some integer k, Tin) ^ n/ k for all n. Then we shall say that the sequence a is T-computable if and only if there exists a multitape Turing machine, 3~, which prints the first n digits of the sequence a on its output tape in no more than Tin) operations, n = 1,2, ••», allowing for the possibility of printing a bounded number of digits on one square. The class of all T-computable binary sequences shall be denoted by ST, and we shall refer to T(n) as a time-function. Sr will be called a complexity class.When several symbols are printed on one square, we regard them as components of a single symbol. Since these are bounded, we are dealing with a finite set of output symbols. As long as the output comes pouring out of the machine in a readily understood form, we do not regard it as unnatural that the output not be strictly binary. Furthermore, we shall see in Corollaries 2.5, 2.7, and 2.8 that if we insist that Tin) ^ n and that only (single) binary outputs be used, then the theory would be within an e of the theory we are adopting.The reason for the condition Tin) ^ n/fc is that we do not wish to regard the empty set as a complexity class. For if a is in ST and F is the machine which prints it, there is a bound k on the number of digits per square of output tape and T can print at most fcn0 d igits in n0 operations. By assumption, Tikn0) ^ n0 or (substituting n0 = n/ k) Tin) à n/ k . On the other hand, Tin) ^ n/ k implies that the sequence of all zeros is in ST because we can print k zeros in each operation and thus ST is not void.Next we shall derive some fundamental properties of our classes.Theorem 1. TAe set of all T-computable binary sequences, ST, is recursively enumerable.Proof. By methods similar to the enumeration of all Turing machines [2] one can first enumerate all multitape Turing machines which print binary sequences. This is just a matter of enumerating all the sets satisfying Definition 1 with the1965] ON THE COMPUTATIONAL C OMPLEXITY O F ALGORITHMS 289 added requirement that Sjo is always a finite sequence of binary digits (regarded as one symbol). Let such an enumeration be &~x, 3~2, ••• . Because T(n) is comput-able, it is possible to systematically modify each ^"¡ to a machine &"'t w ith the following properties : As long as y¡ prints its nth digit within T(n) operations (and this can be verified by first computing T(n) and then looking at the first T(n) operations of ^"¡), then the nth digit of &~'t will be the nth output of &~¡. If &~¡ s hould ever fail to print the nth digit after T(n) operations, then ^"¡'will print out a zero for each successive operation. Thus we can derive a new enumeration •^"'u &~2> "•• If' &\ operates within time T(n), then ^", and ^"¡'compute the same T-computable sequence <x¡. O therwise, &~{ c omputes an ultimately constant sequence a¡ and this can be printed, k bits at a time [where T(n) — n / fc] by a zero tape machine. In either case, a¡ is T-computable and we conclude that {«,} = ST.Corollary 1.1. There does not exist a time-function T such that ST is the set of all computable binary sequences.Proof. Since ST is recursively enumerable, we can design a machine !T which, in order to compute its ith output, computes the z'th bit of sequence a, and prints out its complement. Clearly 3~ produces a sequence a different from all <Xj in ST.Corollary 1.2. For any time-function T, there exists a time-function U such that ST is strictly contained in Sv. Therefore, there are infinitely long chainsSTl cr STl cz •••of distinct complexity classes.Proof. Let &" compute a sequence a not in ST (Corollary 1.1). Let V(n) equal the number of operations required by ^"to compute the nth digit of a. Clearly V is computable and a e Sr. Lett/(n) = max [Tin), V(n)] ,then Vin) is a time-function and clearlyOrí ^3 Oj1 *Since a in Sv and a not in ST, we haveCorollary 1.3. The set of all complexity classes is countable.Proof. The set of enumerable sets is countable.Our next theorem asserts that linear changes in a time-function do not change the complexity class. // r is a real number, we write [r] to represent the smallest integer m such that m = r.290J. HARTMANIS AND R. E. STEARNS[MayTheorem 2. If the sequence cc is T-computable and k is a computable, positive real number, then a is [kT~\-computable; that is,ST = S[kTX.Proof. We shall show that the theorem is true for k = 1/2 and it will be true for fc = 1/ 2m b y induction, and hence for all other computable k since, given k, k ^ 1 /2'" for some m. (Note that if k is computable, then \kT~\ is a computable function satisfying Definition 2.)Let ¡F be a machine which computes a in time T. If the control state, the tape symbols read, and the tape symbols adjacent to those read are all known, then the state and tape changes resulting from the next two operations of &~ are determined and can therefore be computed in a single operation. If we can devise a scheme so that this information is always available to a machine 5~', then &' can perform in one operation what ST does in two operations. We shall next show how, by combining pairs of tape symbols into single symbols and adding extra memory to the control, we can make the information available.In Figure 2(a), we show a typical tape of S" with its head on the square marked 0. In Figure 2(b), we show the two ways we store this information in &~'. Each square of the ^"'-tape contains the information in two squares of the ^-tape. Two of the ^"-tape symbols are stored internally in 3r' and 3~' must also remember which piece of information is being read by 9~. In our figures, this is indicated by an arrow pointed to the storage spot. In two operations of &~, t he heads must move to one of the five squares labeled 2, 1,0, — l,or —2. The corresponding next position of our ^"'-tape is indicated in Figures 2(c)-(g). It is easily verified that in each case, &"' can print or store the necessary changes. In the event that the present symbol read by IT is stored on the right in ¡T' as in Figure 2(f), then the analogous changes are made. Thus we know that ST' can do in one operation what 9~ does in two and the theorem is proved.Corollary 2.1. If U and T are time-functions such that«-.«> Vin)then Svçz ST.Proof. Because the limit is greater than zero, Win) ^ Tin) for some k > 0, and thus Sv = SlkVj çz sT.Corollary 2.2. If U and T are time-functions such thatTin)sup-TTT-r- < 00 ,n-»a> O(n)then SV^ST.Proof. This is the reciprocal of Corollary 2.1.1965] ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMSE37291/HO W2|3l4[5l(/ZEEI33OÏÏT2Ï31/L-2_-iJ(c]¿m W\2I3I4I5K/(b)ZBE o2|3|4l5|\r2Vi!¿En on2l3l4l5|/l-T-i](d)¿BE2 34[5|6|7ir\10 l|(f)¿m2 34|5l6l7l /L<Dj(g)Figure 2. (a) Tape of ^" with head on 0. (b) Corresponding configurations of 9"'. (c) 9~' if F moves two left, (d) 9~> i f amoves to -1. (e) 9~' if ^~ moves to 0. (f)^"' if amoves to 1.(g) 9~' if 3~ moves two rightCorollary 2.3. If U and T are time-functions such thatTin)0 < hm ) ; < oo ,H-.« Uin)then Srj = ST .Proof. This follows from Corollaries 2.1 and 2.2.Corollary 2.4. // Tin) is a time-function, then Sn^ST . Therefore, Tin) = n is the most severe time restriction.Proof. Because T is a time-function, Tin) = n/ k for some positive k by Definition 2; hence292j. hartmanis and r. e. stearns[Maymf m à 1 > O…-»o, n kand S… çz s T by Corollary 2.1.Corollary 2.5. For any time-function T, Sr=Sv where t/(n)=max \T(n),n\. Therefore, any complexity class may be defined by a function U(n) ^ n. Proof. Clearly inf (T/ Í7) > min (1,1/ k) and sup (T/ U) < 1 .Corollary 2.6. If T is a time-function satisfyingTin) > n and inf -^ > 1 ,…-co nthen for any a in ST, there is a multitape Turing machined with a binary (i.e., two symbol) output which prints the nth digit of a in Tin) or fewer operations. Proof. The inf condition implies that, for some rational e > 0, and integer N, (1 - e) Tin) > n or Tin) > eTin) + n for all n > N. By the theorem, there is a machine 9' which prints a in time \zT(ri)\. 9' can be modified to a machine 9" which behaves like 9' except that it suspends its calculation while it prints the output one digit per square. Obviously, 9" computes within time \i.T(ri)\ + n (which is less than Tin) for n > N). $~" can be modified to the desired machine9~ by adding enough memory to the control of 9~" to print out the nth digit of a on the nth operation for n ^ N.Corollary 2.7. IfT(n)^nandoieST,thenforanys >0, there exists a binary output multitape Turing machine 9 which prints out the nth digit of a in [(1 + e) T(n)J or fewer operations.Proof. Observe that. [(1 + e) T(n)]inf —--——■— — 1 + enand apply Corollary 2.6.Corollary 2.8. // T(n)^n is a time-function and oteST, then for any real numbers r and e, r > e > 0, /Aere is a binary output multitape Turing machine ¡F which, if run at one operation per r—e seconds, prints out the nth digit of a within rT(n) seconds. Ifcc$ ST, there are no such r and e. Thus, when considering time-functions greater or equal to n, the slightest increase in operation speed wipes out the distinction between binary and nonbinary output machines.Proof. This is a consequence of the theorem and Corollary 2.7.Theorem 3. // Tx and T2 are time-functions, then T(n) = min [T^n), T2(n)~] is a time-function and STí O ST2 = ST.1965] ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMS 293 Proof. T is obviously a time-function. If 9~x is a machine that computes a in time T, and 9~2 computes a in time T2, then it is an easy matter to construct a third device &~ i ncorporating both y, and 3T2 which computes a both ways simul-taneously and prints the nth digit of a as soon as it is computed by either J~x or 9~2. Clearly this machine operates inTin) = min \Txin), T2(n)] .Theorem 4. If sequences a and ß differ in at most a finite number of places, then for any time-function T, cceST if and only if ße ST.Proof. Let ,T print a in time T. Then by adding some finite memory to the control unit of 3", we can obviously build a machine 3~' which computes ß in time T.Theorem 5. Given a time-function T, there is no decision procedure to decide whether a sequence a is in ST.Proof. Let 9~ be any Turing machine in the classical sense and let 3Tx be a multitape Turing machine which prints a sequence ß not in ST. Such a 9~x exists by Theorem 1. Let 9~2 be a multitape Turing machine which prints a zero for each operation $~ makes before stopping. If $~ should stop after k operations, then 3~2 prints the /cth and all subsequent output digits of &x. Let a be the sequence printed by 9"2, Because of Theorem 4, a.eST if and only if 9~ does not stop. Therefore, a decision procedure for oceST would solve the stopping problem which is known to be unsolvable (see [2]).Corollary 5.1. There is no decision procedure to determine if SV=ST or Sv c STfor arbitrary time-functions U and T.Proof. Similar methods to those used in the previous proof link this with the stopping problem.It should be pointed out that these unsolvability aspects are not peculiar to our classification scheme but hold for any nontrivial classification satisfying Theorem 4.III. Other devices. The purpose of this section is to compare the speed of our multitape Turing machine with the speed of other variants of a Turing machine. Most important is the first result because it has an application in a later section.Theorem 6. If the sequence a is T-computable by multitape Turing machine, !T, then a is T2-computable by a one-tape Turing machine 3~x .Proof. Assume that an n-tape Turing machine, 3~, is given. We shall now describe a one-tape Turing machine Px that simulates 9~, and show that if &" is a T-computer, then S~x is at most a T2-computer.294j. hartmanis and r. e. stearns[May The S~ computation is simulated on S'y as follows : On the tape of & y will be stored in n consecutive squares the n symbols read by S on its n tapes. The symbols on the squares to the right of those symbols which are read by S~ on its n tapes are stored in the next section to the right on the S'y tape, etc., as indicated in Figure 3, where the corresponding position places are shown. The1 TAPE T|A 1 TAPE T2I?TAPE Tn(a)J-"lo(b)Figure 3. (a) The n tapes of S. (b) The tape of S~\machine Tx operates as follows: Internally is stored the behavioral description of the machine S", so that after scanning the n squares [J], [o], ■■■, [5]»-^"îdetermines to what new state S~ will go, what new symbols will be printed by it on its n tapes and in which direction each of these tapes will be shifted. First,¡Fy prints the new symbols in the corresponding entries of the 0 block. Then it shifts the tape to the right until the end of printed symbols is reached. (We can print a special symbol indicating the end of printed symbols.) Now the machine shifts the tape back, erases all those entries in each block of n squares which correspond to tapes of S~ which are shifted to the left, and prints them in the corresponding places in the next block. Thus all those entries whose corresponding S~ tapes are shifted left are moved one block to the left. At the other end of the tape, the process is reversed and returning on the tape 9y transfers all those entries whose corresponding S~ tapes are shifted to the right one block to the right on the S'y tape. When the machine S', reaches the rigAz most printed symbol on its tape, it returns to the specially marked (0) block which now contains1965] ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMS 295 the n symbols which are read by &~ o n its next operation, and #", has completed the simulation of one operation of 9~. It can be seen that the number of operations of Tx is proportional to s, the number of symbols printed on the tape of &"¡. This number increases at most by 2(n + 1) squares during each operation of &. Thus, after T(fc) operations of the machine J~, the one-tape machine S"t will perform at most7(*)T,(fc) =C0+ T Cxii = loperations, where C0 and C, are constants. But thenr,(fe) g C2 £ i^C [T(fc)]2 .¡ =iSince C is a constant, using Theorem 2, we conclude that there exists a one tape machine printing its fcth output symbol in less than T(fc)2 tape shifts as was to be shown.Corollary 6.1. The best computation time improvement that can be gained in going from n-tape machines to in + l)-tape machines is the square root of the computation time.Next we investigate what happens if we allow the possibility of having several heads on each tape with some appropriate rule to prevent two heads from occupy-ing the same square and giving conflicting instructions. We call such a device a multihead Turing machine. Our next result states that the use of such a model would not change the complexity classes.Theorem 7. Let a. be computable by a multihead Turing machine 3T which prints the nth digit in Tin) or less operations where T is a time-function; then a is in ST .Proof. We shall show it for a one-tape two-head machine, the other cases following by induction. Our object is to build a multitape machine Jr' which computes a within time 4T which will establish our result by Theorem 2. The one tape of !T will be replaced by three tapes in 9"'. Tape a contains the left-hand information from 9", tape b contains the right-hand information of 9~, and tape c keeps count, two at a time, of the number of tape squares of ST which are stored on both tapes a and b_. A check mark is always on some square of tape a to indicate the rightmost square not stored on tape b_ and tape b has a check to indicate the leftmost square not stored on tape a.When all the information between the heads is on both tapes a and b. then we have a "clean" position as shown in Figure 4(a). As &" operates, then tape296j. hartmanis and r. e. stearns [May7/Fio TTzTTR" 5 "6Ï7M I 4T5T6" 7 8TT77' ^f(a) rT-Tô:TT2l3l4l?l \J ¿Kh.1y(b) J I l?IM2!3|4 5.6T7 /I |?|4,|5|6 7 8TT7(c) f\7~ /\V\/\A7\7M J M/l/yTITTTTTTJ(a) (b)Figure 4. (a) .^"' in clean position, (b) S' in dirty positiona performs like the left head of S~, tape A behaves like the right head, and tape c reduces the count each time a check mark is moved. Head a must carry the check right whenever it moves right from a checked square, since the new symbol it prints will not be stored on tape A; and similarly head A moves its check left.After some m operations of S~' corresponding to m operations of S~, a "dirty"position such as Figure 4(b) is reached where there is no overlapping information.The information (if any) between the heads of S~ must be on only one tape of S~',say tape A as in Figure 4(b). Head A then moves to the check mark, the between head information is copied over onto tape a, and head amoves back into position.A clean position has been achieved and S~' is ready to resume imitating S~. The time lost is 3/ where I is the distance between the heads. But / ^ m since headA has moved / squares from the check mark it left. Therefore 4m is enough time to imitate m operations of S~ and restore a clean position. Thusas was to be shown.This theorem suggests that our model can tolerate some large deviations without changing the complexity classes. The same techniques can be applied to other changes in the model. For example, consider multitape Turing ma-chines which have a fixed number of special tape symbols such that each symbol can appear in at most one square at any given time and such that the reading head can be shifted in one operation to the place where the special symbol is printed, no matter how far it is on the tape. Turing machines with such "jump instructions^ are similarly shown to leave the classes unchanged.Changes in the structure of the tape tend to lead to "square laws." For example,consider the following :Definition 3. A two-dimensional tape is an unbounded plane which is sub-divided into squares by equidistant sets of vertical and horizontal lines as shown in Figure 5. The reading head of the Turing machine with this two-dimensional tape can move either one square up or down, or one square left or right on each operation. This definition extends naturally to higher-dimensional tapes.。

高三现代科技前沿探索英语阅读理解20题1<背景文章>Artificial intelligence (AI) is rapidly transforming the field of healthcare. In recent years, AI has made significant progress in various aspects of medical care, bringing new opportunities and challenges.One of the major applications of AI in healthcare is in disease diagnosis. AI-powered systems can analyze large amounts of medical data, such as medical images and patient records, to detect diseases at an early stage. For example, deep learning algorithms can accurately identify tumors in medical images, helping doctors make more accurate diagnoses.Another area where AI is making a big impact is in drug discovery. By analyzing vast amounts of biological data, AI can help researchers identify potential drug targets and design new drugs more efficiently. This can significantly shorten the time and cost of drug development.AI also has the potential to improve patient care by providing personalized treatment plans. Based on a patient's genetic information, medical history, and other factors, AI can recommend the most appropriate treatment options.However, the application of AI in healthcare also faces some challenges. One of the main concerns is data privacy and security. Medicaldata is highly sensitive, and ensuring its protection is crucial. Another challenge is the lack of transparency in AI algorithms. Doctors and patients need to understand how AI makes decisions in order to trust its recommendations.In conclusion, while AI holds great promise for improving healthcare, it also poses significant challenges that need to be addressed.1. What is one of the major applications of AI in healthcare?A. Disease prevention.B. Disease diagnosis.C. Health maintenance.D. Medical education.答案：B。

量子计算中英文2019英文FROM BITS TO QUBITS, FROM COMPUTING TO QUANTUM COMPUTING: AN EVOLUTION ON THE VERGE OF A REVOLUTION IN THE COMPUTINGLANDSCAPEPi rjan Alexandru; Petroşanu Dana-Mihaela.ABSTRACTThe "Quantum Computing" concept has evolved to a new paradigm in the computing landscape, having the potential to strongly influence the field of computer science and all the fields that make use of information technology. In this paper, we focus first on analysing the special properties of the quantum realm, as a proper hardware implementation of a quantum computing system must take into account these properties. Afterwards, we have analyzed the main hardware components required by a quantum computer, its hardware structure, the most popular technologies for implementing quantum computers, like the trapped ion technology, the one based on superconducting circuits, as well as other emerging technologies. Our study offers important details that should be taken into account in order to complement successfully the classical computer world of bits with the enticing one of qubits.KEYWORDS: Quantum Computing, Qubits, Trapped Ion Technology, Superconducting Quantum Circuits, Superposition, Entanglement, Wave-Particle Duality, Quantum Tunnelling1. INTRODUCTIONThe "Quantum Computing" concept has its roots in the "Quantum Mechanics" physics subdomain that specifies the way how incredibly small particles, up to the subatomic level, behave. Starting from this concept, the Quantum Computing has evolved to a new paradigm in the computing landscape. Initially, the concept was put forward in the 1980s as a mean for enhancing the computing capability required tomodel the way in which quantum physical systems act. Afterwards, in the next decade, the concept has drawn an increased level of interest due to the Shor's algorithm, which, if it had been put into practice using a quantum computing machine, it would have risked decrypting classified data due to the exponential computational speedup potential offered by quantumcomputing [1].However, as the development of the quantum computing machines was infeasible at the time, the whole concept was only of theoretical value. Nowadays, what was once thought to be solely a theoretical concept, evolved to become a reality in which quantum information bits (entitled "qubits") can be stored and manipulated. Both governmental and private companies alike have an increased interest in leveraging the advantages offered by the huge computational speedup potential provided by the quantum computing techniques in contrast to traditional ones [2].One of the aspects that make the development of quantum computers attractive consists in the fact that the shrinkage of silicon transistors at the nanometer scale that has been taking place for more than 50 years according to Moore's law begins to draw to a halt, therefore arising the need for an alternate solution [3].Nevertheless, the most important factor that accounts for boosting the interest in quantum computing is represented by the huge computational power offered by these systems and the fact that their development from both hardware and software perspectives has become a reality. Quantum computing managed to surpass the computability thesis of ChurchTuring, which states that for any computing device, its power computation could increase only in a polynomial manner when compared to a "standard" computer, entitled the Turing machine [4].During the time, hardware companies have designed and launched "classical" computing machines whose processing performance has been improving over the time using two main approaches: firstly, the operations have been accelerated through an increased processing clock frequency and secondly, through an increase in the number of operations performed during each processing clock's cycle [5].Although the computing processing power has increased substantially after having applied the above-mentioned approaches, the overall gain has remained inaccordance with the thesis of Church-Turing. Afterwards, in 1993, Bernstein and Vazirani have published in [6] a theoretical analysis stating that the extended Church-Turing thesis can be surpassed by means of quantum computing. In the following year, Peter Shor has proved in his paper that by means of quantumcomputing the factorization of a large number can be achieved with an exponentially computing speedup when compared to a classical computing machine [7-9]. Astonishing as the theoretical framework was, a viable hardware implementation was still lacking at the time.The first steps for solving this issue have been made in 1995, when scientists have laid the foundations for a technology based on a trapped ion system [10] and afterwards, in 1999, for a technology employing superconducting circuits [11]. Based on the advancement of technology, over the last decades, researchers have obtained huge progress in this field, therefore becoming able to build and employ the first quantum computing systems.While in the case of a classical computing machine the data is stored and processed as bits (having the values 0 or 1), in the case of a quantum computingmachine, the basic unit of quantum information under which the data is stored and processed is represented by the quantum bits, or qubits that can have besides the values of 0 and 1, a combination of both these values in the same time, representing a "superposition" of them [12].At a certain moment in time, the binary values of the n bits corresponding to a classical computer define a certain state for it, while in the case of a quantumcomputer, at a certain moment in time, a number of n qubits have the possibility to define all the classical computer's states, therefore covering an exponential increased computational volume. Nevertheless, in order to achieve this, the qubits must be quantum entangled, a non-local property that makes it possible for several qubits to be correlated at a higher level than it was previously possible in classical computing. In this purpose, in order to be able to entangle two or several qubits, a specific controlled environment and special conditions must be met [13].During the last three decades, a lot of studies have been aiming to advance thestate of knowledge in order to attain the special conditions required to build functional quantum computing systems. Nowadays, besides the most popular technologies employed in the development of quantum computing systems, namely the ones based on trapped ion systems and superconducting circuits, a wide range of other alternative approaches are being extensively tested in complex research projects in order to successfully implement qubits and achieve quantum computing [14].One must take into account the fact that along with the new hardware architectures and implementations of quantum computing systems, new challenges arise from the fact that this new computing landscape necessitates new operations, computing algorithms, specialized software, all of these being different than the ones used in the case of classical computers.A proper hardware implementation of a quantum computing system must take into account the special properties of the quantum realm. Therefore, this paper focuses first on analyzing these characteristics and afterwards on presenting the main hardware components required by a quantum computer, its hardware structure, the most popular technologies for implementing quantum computers, like the trapped ion technology, the one based on superconducting circuits, as well as other emerging technologies. Our developed research offers important details that should be taken into account in order to complement successfully the classical computer world of bits with the enticing one of qubits.2.SPECIAL PROPERTIES OF THE QUANTUM REALMThe huge processing power of quantum computers results from the capacity of quantum bits to take all the binary values simultaneously but harnessing this vast amount of computational potential is a challenging task due to the special properties of the quantum realm. While some of these special properties bring considerable benefits towards quantum computing, there are others that can hinder the whole process.One of the most accurate and extensively tested theory that comprehensibly describes our physical world is quantum mechanics. While this theory offers intuitive explanations for large-scale objects, while still very accurate also at the subatomiclevel, the explanations might seem counterintuitive at the first sight. At the quantum level, an object does not have a certain predefined state, the object can behave like a particle when a measurement is performed upon it and like a wave if left unmeasured, this representing a special quantum property entitled wave-particle duality [15].The global state of a quantum system is determined by the interference of the multitude of states that the objects can simultaneously have at a quantum level, the state being mathematically described through a wave function. Actually, the system's state is often described by the sum of the different possible states of its components, multiplied by a coefficient consisting in a complex number, representing, for each state, its relative weight [16, 17]. For such a complex coefficient, by taking into consideration its trigonometric (polar) form, one can write it under the form Aew = A(cos6 + i sind), where A > 0 represents the module of this complex number and is denoted as the "amplitude", while в represents the argument of the complex number, being denoted as "the phase shift". Therefore, the complex coefficient is known if the two real numbers A and в are known.All the constitutive components of a quantum system have wave-like properties, therefore being considered "coherent". In the case of coherence, the different states of the quantum components interact between them, either in a constructive manner or in a destructive one [1]. If a quantum system is measured at a certain moment, the system exposes only a single component, the probability of this event being equal to the squared absolute value of the corresponding coefficient, multiplied by a constant. If the quantum system is measured, from that moment on it will behave like a classical system, therefore leading to a disruption of its quantum state. This phenomenon causes a loss of information, as the wave function is collapsed, and only a single state remains. As a consequence of the measurement, the wave function associated to the quantum obj ect corresponds only to the measured state [1, 17].Considering a qubit, one can easily demonstrate that its quantum state could be represented by a linear superposition of two vectors, in a space endowed with a scalar product having the dimension 2. The orthonormal basis in this space consists of thevectors denoted as |0 >= [Jj and |1 >= [°j. If one considers two qubits, they could be represented as a linear combination of the 22 elements of the base, namely the ones denoted as .... Generally, in the case of n qubits, they could be represented by a superposition state vector in a space having the dimension 2n [2].Another special property of the quantum realm consists in the entanglement, a property that has the ability to exert a significant influence on quantumcomputing and open up a plethora of novel applications. The physical phenomenon of quantum entanglement takes place when two (or more) quantumobjects are intercorrelated and therefore the state of a quantum object influences instantaneously the state(s) of the other(s) entangled quantum object(s), no matter the distance(s) between these objects [16].Another important quantum mechanical phenomenon that plays a very important role in quantum computing is quantum tunneling that allows a subatomic particle to go through a potential barrier, which otherwise would have been impossible to achieve, if it were to obey only the physical laws of classical mechanics. An explanation of this different behavior consists in the fact that in quantum mechanics the matter is treated both as waves and particles, as we have described above, when we have presented the wave-particle duality concept [15].The Schrödinger equation describes the variation of the wave function, taking into account the energy environment that acts upon a quantum system, therefore highlighting the way in which this quantum system evolves. In order to obtain the mathematical description of the environment, of the energies corresponding to all the forces acting upon the system, one uses the Hamiltonian of the quantum system. Therefore, the control of a quantum system can be achieved by controlling its energy environment, which can be obtained by isolating the system from the external forces, and by subjecting the system to certain energy fields as to induce a specific behavior. One should note that a perfect isolation of the quantum system from the external world cannot be achieved, therefore in practice the interactions are minimized as much as possible. Over time, the quantum system is continuously influenced to a small extent by the external environment, through a process called "decoherence",process that modifies the wave function, therefore collapsing it to a certain degree [1].Figure 1 depicts the main special properties of the quantum realm, which, when precisely controlled, have the ability to influence to a large extent the performance of a quantum computer implementation, and open up new possibilities for innovation concerning the storing, manipulation and processing of data.In the following, we analyze a series of hardware components and existing technologies used for developing and implementing quantum computers.3.AN OVERVIEW OF THE NECESSARY HARDWARE AND OF THE EXISTING TECHNOLOGIES USED IN THE IMPLEMENTATIONS OF QUANTUM COMPUTERSA proper hardware architecture is vital in order to be able to program, manipulate, retrieve qubits and overall to achieve an appropriate and correct quantumcomputer implementation. When implementing a quantum computer at the hardware level, one must take into account the main hardware functions, a proper modularization of the equipment along with both similarities and differences between quantum and classic computer implementations. Conventional computers are an essential part in the successful implementation of a quantum computer, considering the fact that after having performed its computation, a quantumcomputer will have to interact with different categories of users, to store or transmit its results using classic computer networks. In order to be efficient, quantum computers need to precisely control the qubits, this being an aspect that can be properly achieved by making use of classic computing systems.The scientific literature [1, 18, 19] identifies four abstract layers in the conceptual modelling process of quantum computers. The first layer is entitled the "quantum data plane" and it is used for storing the qubits. The second layer, called "control and measurement plane", performs the necessary operations and measurement actions upon the qubits. The third layer entitled "control processor plane" sets up the particular order of operations that need to be performed along with the necessary measurement actions for the algorithms, while the fourth abstract layer, the "host processor", consists in a classical computer that manages the interface withthe different categories of personnel, the storage of data and its transmission over the networks.In the following, we present the two most popular technologies employed in the development of quantum computing systems, namely the ones based on trapped ion systems and superconducting circuits and, afterwards, other alternative approaches that are being extensively tested in complex research projects in order to successfully implement qubits and achieve quantum computing.By means of trapping atomic ions, based on the theoretical concepts presented by Cirac et al within [20], in 1995, Monroe et al [21] revealed the first quantumlogic gate. This was the starting point in implementing the first small scale quantum processing units, making it possible to design and implement a rich variety of basic quantum computing algorithms. However, the challenges to scale up the implementations of quantum computers based on the trapped ion technology are enormous because this process implies a synergy of complex technologies like coherent electronic controllers, laser, radio frequency, vacuum, microwave [1, 22].In the case of a quantum computer based on the trapped atomic ions technology, the qubits are represented by atomic ions contained within the quantum data plane by a mechanism that keeps them in a certain fixed location. The desired operations and measurement actions are performed upon the qubits using accurate lasers or a source of microwave electromagnetic radiation in order to alter the states of the quantum objects, namely the atomic ions. In order to reduce the velocity of the quantum objects and perform measurements upon them, one uses a laser beam, while for assessing the state of the ions one uses photon detectors [14, 23, 24]. Figure 2 depicts an implementation of the quantum trapping atomic ions technology.Another popular technology used in the development and implementation of quantum computers is based on superconducting quantum circuits. These quantum circuits have the property of emitting quantized energy when exposed to temperatures of 10-3K order, being referred in the literature as "superconducting artificial atoms" [25]. In contrast to classic integrated circuits, the superconducting quantum circuits incorporate a distinctive characteristic, namely a"Josephson junction" that uses wires made of superconducting materials in order to achieve a weak connection. The common way of implementing the junction consists in using an insulator that exposes a very thin layer and is created through the Niemeyer-Dolan technique which is a specialized lithographic method that uses thin layers of film in order to achieve overlapping structures having a nanometer size [26].Superconducting quantum circuits technology poses a series of important advantages, offering red3uced decoherence and an improved scale up potential, being compatible with microwaves control circuits, operating with time scales of the nanosecond order [1]. All of these characteristics make the superconducting quantum circuits an attractive and performant technique in developing quantum computers. A superconducting quantum circuit developed by D-Wave Systems Inc. is depicted in Figure 3.In order to overcome the numerous challenges regarding the scaling of quantum computers developed based on trapped ion systems and superconducting circuits, many scientists focus their research activity on developing emerging technologies that leverage different approaches for developing quantumcomputers.One of the alternatives that scientists investigate consists in making use of the photons' properties, especially of the fact that photons have a weak interaction between each other and also with the environment. The photons have been tested in a series of quantum experiments and the obtained results made the researchers remark that the main challenge in developing quantum computers through this approach is to obtain gates that operate on spaces of two qubits, as at the actual moment the photons offer very good results in terms of single qubit gates. In order to obtain the two-qubit gates, two alternative approaches are extensively being investigated as these have provided the most promising results.The first approach is based on operations and measurements of a single photon, therefore creating a strong interaction, useful in implementing a probabilistic gate that operates on a space of two qubits [1]. The second alternative approach employs semiconductor crystals structures of small dimensions in order to interact with the photons. These small structures can be found in nature, case in which they are called"optically active defects", but can also be artificially created, case in which they are called "quantum dots". An important challenge that must be overcome when analyzing quantum computers based on photons is their size. Until now, the development of this type of computers has been possible only for small dimensions, as a series of factors limit the possibility to increase the dimensions of photon quantum computers: the very small wavelengths of the photons (micron-size), their very high speed (the one of the light), the direction of their movement being along a certain dimension of the optical chip. Therefore, trying to significantly increase the number of qubits (represented by the photons) proves to be a difficult task in the case of a photonic device, much more difficult than in the case of other systems, in which the qubits are located in space. Nevertheless, the evolution of this emerging technology promises efficient implementations in the near future [27].Another technology that resembles the one of "trapping atomic ions" for obtaining qubits consists in the use and manipulation of neutral atoms by means of microwave radiation, lasers and optics. Just like in the case of the trapping atomic ions technology, the "cooling" process is achieved using laser sources. According to [1, 28], in 2018 there were implemented successfully quantum systems having 50 qubits that had a reduced space between them. By means of altering the space between the qubits, these quantum systems proved to be a successful analog implementation of quantum computers. In what concerns the error rates, according to [29], in 2018 there have been registered values as low as 3% within two-qubit quantum systems that managed to isolate properly the operations performed by nearby qubits. Since there are many similarities between the two technologies, the scaling up process faces a lot of the problems of the "trapping atomic ions" technology. However, the use of the neutral atoms technology offers the possibility of creating multidimensional arrays.A classification of semiconductor qubits is made according to the method used to manipulate the qubits that can be achieved either by photon manipulation or by using electrical signals. Quantum dots are used in the case of semiconductor qubits that are gated by optical means in order to assure a strong coupling of the photons while in the case of semiconductor qubits manipulated via electrical signals, voltages are usedupon lithographically metal gates for manipulating the qubits [1]. This quantum technology, although being less popular than other alternatives, resembles the existing classical electronic circuits, therefore one might argue that it has a better chance in attracting considerable investments that eventually will help speed up the scaling up process of quantum computers implementation.In order to scale up qubits that are optically gated, one needs a high degree of consistency and has to process every qubit separately at the optical level. In [30], Pla et al. state that even if the qubits that are gated electrically can be very dense, the material related problems posed not long-ago serious quality problems up to single qubits gates level. Although the high density provided by this type of quantum technology creates opportunities for integrating a lot of qubits on a single processor, complex problems arise when one has to manipulate this kind of qubits because the wiring will have to assure an isolation of the control signals as to avoid interference and crosstalk.Another ongoing approach in developing quantum computers consists in using topological qubits within which the operations to be performed upon are safeguarded due to a microscopically incorporated topological symmetry that allows the qubit to correct the errors that may arise during the computing process [1]. If in the future this approach materializes, the computational cost associated with correcting the quantum errors will diminish considerably or even be eliminated altogether. Although this type of technology is still in its early stages, if someday one is able to implement it and prove its technical feasibility, the topological quantum computers will become an important part of the quantum computing landscape.4. CONCLUSIONSQuantum computing represents a field in a continuous evolution and development, a huge challenge in front of researchers and developers, having the potential to influence and revolutionize the development of a wide range of domains like the computing theory, information technology, communications and, in a general framework, regarding from the time perspective, even the evolution and progress of society itself. Therefore, each step of the quantum computers' evolution has thepotential to become of paramount importance for the humanity: from bits to qubits, from computing to quantum computing, an evolution on the verge of a revolution in the computing landscape.中文从比特到量子比特，从计算到量子计算：计算机革命的演变抽象“量子计算”的概念已发展成为计算领域的一个新范例，具有极大地影响计算机科学领域和所有利用信息技术的领域的潜力。

【经济学人】双语阅读：超级计算更深奥的思维Science and technology科学技术Supercomputing超级计算Deeper thought更深奥的思维The world has a new fastest computer, thanks to video games多亏电子游戏，让世界拥有了一台新的最快的计算机The ultimate games machine终极游戏机SPEED fanatics that they are, computer nerds like to check the website of Top500, a collaboration between German and American computer scientists that keeps tabs on which of the world's supercomputers is the fastest.作为速度控，电脑迷们喜欢查看Top500的网站，该网站是由德国和美国的计算机科学家合办，记录世界上最快的超级计算机。

On November 12th the website released its latest list, and unveiled a new champion.11月12日，该网站发布了最新榜单，揭开了新一任冠军的面纱。

The computer in question is called Titan, and it lives at Oak Ridge National Laboratory, in Tennessee.获得冠军的计算机名为泰坦，居于田纳西州的橡树岭国家实验室，It took first place from another American machine, IBM's Sequoia, which is housed at Lawrence Livermore National Laboratory, in California.它是击败了另一台美国的计算机-IBM的红杉而取得冠军的，红杉位于加利福尼亚州的劳伦斯利物莫国家实验室。

黎曼猜想英语The Riemann Hypothesis, named after the 19th-century mathematician Bernhard Riemann, is one of the most profound and consequential conjectures in mathematics. It is concerned with the distribution of the zeros of the Riemann zeta function, a complex function denoted as $$\zeta(s)$$, where $$s$$ is a complex number. The hypothesis posits that all non-trivial zeros of this analytical function have their real parts equal to $$\frac{1}{2}$$.To understand the significance of this conjecture, one must delve into the realm of number theory and the distribution of prime numbers. Prime numbers are the building blocks of arithmetic, as every natural number greater than 1 is either a prime or can be factored into primes. The distribution of these primes, however, has puzzled mathematicians for centuries. The Riemann zeta function encodes information about the distribution of primes through its zeros, and thus, the Riemann Hypothesis is directly linked to understanding this distribution.The zeta function is defined for all complex numbers except for $$s = 1$$, where it has a simple pole. For values of $$s$$ with a real part greater than 1, it converges to a sum over the positive integers, as shown in the following equation:$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$$。

课时练12篇阅读＋1篇完形Ⅰ.阅读理解A(2020·合肥高三调研)Rich as a KingWilliamⅠ，who conquered England some 950 years ago, had wealth,power and an army. Yet although William was very rich by the standard ofhis time, he had nothing like a flush toilet(抽水马桶), paper towels, or ariding lawn mower(割草机). How did he get__by?History books are filled with wealthy people who were poor comparedto me. I have storm windows, Croesus did not. Entire nations trembled before Alexander the Great, but he couldn’t buy cat food. Czar Nicholas lacked an electric saw.Given how much better off I am than so many famous dead people, you’d think I’d be content. The trouble is that, like most people, I compare my wealth with that of living persons: neighbors, school classmates, and famous TV people. The greed I feel toward my friend Howard’s new kitchen is not reduced by the fact that no kings ever had a refrigerator with glass doors.There is really no rising or falling standard of living. Over the centuries people simply find different things to feel sad about. You’d think that simply not having disease would put us in a good mood, but no, we want a hot bath too.Of course, one way to achieve happiness would be to realize that even by today’s standards the things I own are pretty nice. My house is smaller than the houses of many investment bankers, but even so it has a lot more rooms that my wife and I can keep clean.Besides, to people looking back at our era from a century or two in the future, these bankers’fancy counter tops and my own worn Formica will seem equally shabby. I can’t keep up with my neighbors right now. But just wait.【解题导语】本文主要通过同富有的古人对比启迪读者：生活没有必要攀比，要知足常乐。

Unit 31The first mistake is to think of mankind as a thing in itself. It isn’t.第一个错误是把人看作是某种独立的事物。

其实并不是。

It is part of an intricate web of life.人是复杂的生命网络系统中的一部分。

And we can’t think even of life as a thing in itself. It isn’t.我们甚至不能将生命本身视为某种独立的事物。

它确实不是。

It is part of the intricate structure of a planet bathed by energy from the Sun. 生命是一颗沐浴着太阳能的行星上的复杂结构的一部分。

2The Earth, in the nearly 5 billion years since it assumed approximately its present form, has undergone a vast evolution.地球自从呈目前的形状近 50 亿年以来，已经历了一场巨大的演变。

When it first came into being, it very likely lacked what we would today call an ocean and an atmosphere. 在形成的初期，地球上很可能没有我们今天称之为海洋和大气层之类的东西。

These were formed by the gradual outward movement of material as the solid interior settled together.当地球的内部固体紧压在一起时，物质的逐渐向外运动就形成了海洋和大气层。

3Nor were ocean, atmosphere, and solid crust independent of each other after formation. 地球形成之后，海洋、大气层以及坚固的地壳之间也并非相互独立。

高中英语科技前沿词汇单选题50题1. In the field of computer science, when we talk about data storage, "cloud computing" provides a ______ solution.A. revolutionaryB. traditionalC. limitedD. temporary答案：A。

本题考查词汇含义。

“revolutionary”意为“革命性的”，“cloud computing”（云计算）在数据存储方面提供的是一种革命性的解决方案。

“traditional”表示“传统的”，不符合云计算的特点。

“limited”指“有限的”，与云计算的强大存储能力不符。

“temporary”意思是“临时的”，也不符合云计算作为长期数据存储方式的特性。

2. The development of artificial intelligence requires advanced algorithms and powerful ______.A. processorsB. memoriesC. screensD. keyboards答案：A。

“processors”是“处理器”，人工智能的发展需要先进算法和强大的处理器。

“memories”是“内存”，内存并非发展人工智能的关键硬件。

“screens”是“屏幕”，对人工智能发展并非核心硬件。

“keyboards”是“键盘”，与人工智能发展所需的硬件无关。

3. In the era of big data, ______ plays a crucial role in extracting valuable information.A. data miningB. data hidingC. data deletingD. data adding答案：A。

“data mining”是“数据挖掘”，在大数据时代，数据挖掘在提取有价值信息方面起着关键作用。