For a long time not much importance has been given to the physical modalities around which a calculation device could be realized. Only recently, extrapolating the relentless progress of the practical technology of modern computers, it has been perceived that the physical principles upon which a calculating machine is built have a operational impact on its ability to transform an insoluble problem to a soluble problem. Richard Feynman, reflecting on this second possibility, conceived of a machine working on the base of the principles of new quantum physics and so of opening a promising new chapter in computer science.

In 1981, the Institute Massachusetts of Technology (MIT) hosted the first convention on the relationship that exists between physics and computation. Feynman, introduced one idea in a Paper entitled "Simulating Physics with Computers". Feynman did not see anything particularly exciting in the approximate computer simulations of reality made until that date. In his paper, Feynman was, instead, interested in the possibility of obtaining an exact simulation of Nature in a computer.

Feynman grasped that computation was not only a mathematical discipline, but also a physical one.

The simulation of a phenomenon on a classic computer requires an predictable deterministic world. There are no uncertainties in the behavior of circuits constituted from billions of trillions of atoms and electrons. "But can a traditional computer of that time can emulate the quantum world?" asked Feynman.

The argument, over a period of forty years' research, has produced a remarkable output of theoretical work; it turns out that developments leading to designs for possible hardware can be expected in the near future.

Here it will be enough to say that the entire body of "Classical Information Theory" from C. Shannon onwards, is up for revision.

The traditional definition of the unit of information - the bit - is an unavoidably classical concept, based upon a classical operating bistable circuit ( "On-Off" switch), which must be revised when you base switching operations on quantum phenomena, such as the spin of an electron or the polarization of a photon.

The Qubit - the new unit of information based on quantum phenomena - must now be set alongside the Bit, based on classical phenomena. The concept of informative entropy must opportunely be revised. In effect, the concept of accessible information, or the effective information which can successfully be retrieved from a quantum system for making a measurement, must be reviewed as well; this is most important in estimating the theoretical possibility of designing physical systems with which to carry out operations beyond the reach of the classic techniques of computation.

It is important to observe that the interest in the quantum calculation lies not in repetitive procedures and calculations, which can be executed on conventional computers operating in classic mode, but in the fact that, by means of this new technology, operations that are impossible with the traditional technique can become possible or, at least, operations which are grossly inefficient on classic operating systems can become very much more efficient with QC (Quantum Computing).

It remains however to observe that the problems which can best be solved with QC are rather specialised, whose solutions can be quite perplexing.

The evidence from experiments has shown that microscopic phenomena obey different laws from those of classic physics, which humanity has long believed capable of explaining all of physical reality. In fact, on the one hand, the macroscopic classic phenomena derive from the principle of causality in a strongly determinist sense, while on the other hand, for the quantum microscopic phenomena, the principle of causality of classical physics breaks down.

Heisenberg, on the basis of the observations carried out in the microscopic reality which presented apparently insoluble difficulties in classic terms, proposed that the determinist principle must be jettisoned in favour of the principle of statistical causality. ( Laws of Probability)

Heisenberg's Uncertainty Principle has, in fact, consequences of immense scope, which upset the consolidated certainties of the most obvious daily experience. To the idea that the electrons, the ultimate constituent of matter, are material balls or particles of the smallest dimensions we must add the realisation that, even if they are particles, they behave very differently from our commonsense view, to say the least.

As well as the Uncertainty Principle in quantum physics, there is another principle, known as Principle of Indistinguishability, which states that all microscopic particles of the same type are indistinguishable from each other: that is all elementary particles are identical, and cannot be distinguished from each other either with techniques of coloration, or in any other way.

To the Uncertainty Principle we must another singular fact of microscopic reality - the Principle of Complementarity. According to this principle, there are some complementary properties at the microscopic level which are mutually exclusive, in the sense that the detection of one, by means of experiment, excludes the detection of the other. To give an example, a quantum particle can, from time to time, in different experimental systems, be demonstrated in one form (corpuscle) or in the other (wave), but both aspects can never perceived at the same time. This dual nature of Quantum "particles" is sometimes referred to as the Wave/Particle Duality

On the basis of another principle (the Principle of Superimposition) for the microscopic objects, it is possible that different states of a determined entity, can calmly coexist in a state of non-definition, as a linear combination of several of the states in which it can be found.

Who, looking through the glass of a window, has not sometimes seen not only the external landscape but also his/her own image, more or less clearly? Perhaps if you were watching from other side of the glass, you would see the same landscape partially reflected. This phenomenon usually goes unnoticed, but is in truth an extraordinarily accessible example of the quantum world for Everyone.

Light is known to be constituted of photons. These photons cross the glass in order to show the landscape; but it is not determined. The quantum world of elementary particles, like photons, is not a world of certainties but of probabilities. The photon that hits the glass can cross it, but it can also be reflected: the photon has one sure probability to pass less or through the glass. The phenomenon is more blurred, and defies the Aristotelian logic to which we are used: in which the photon either passes through the glass, or not. The sense of one of the conceptual pillars of the quantum mechanics is this: the superimposition principle. If a quantum entity can assume two values or exist in two states it is in one superimposition of the two, with a non- zero probability of being in one and the other.

In a superimposition, it cannot be said that an entity is found really in one state or another that but that is not known which one; the superimposition contains, instead, all the possible cases, but is not equivalent to some of them. 

At this point two questions naturally arise:

• which classes of problems can be tackled by a quantum computer?

• how can a quantum computer be physically constructed?

It can be assumed that the quantum computer is not a typical computer designed to be annoying on the Internet, or to sending e-mail. What end it can serve, then?

Already it has been observed that, according to the fundamental dogma of computation, in the realm of calculation a machine conceptually more powerful than the Turing machine does not exist.

From the point of view of computing power, an algorithm can be derived from the number of operations, and from the amount of memory required for an input of x dimensions.

This characterization of the algorithm determines the complexity of the same algorithm. Among the problems considered complex are surely those that grow as the power of a number. The function y =x2 grows very quickly. For high values of x it is necessary to execute more and more laborious multiplications. If the power grows further, as an example y =x4 or y =x5 the difficulty increases still. Similar problems, defined polynomials, are today within the capacity of classic computers. But problems exist that grow very more quickly than those polynomials. The problems of exponential type increase more quickly in complexity than those of polynomials: ex grows very more quickly than x3, x5,x 7,per increasing values of x.

The distinction used more today is between problems that can be resolved in apolynomial way (P), and are considered tractable, and those that instead cannot be resolved in a polynomial way which are generally considered intractable; these one can subdivide into various classes. Among these latter there is the so-called class NP. Simplifying, the problems of type NP cannot, in a generalized manner, be resolved from determinist algorithms of polynomial type and are, therefore, intractable. The initials "NP", in fact, stand for non-deterministic polynomial time.

"Non Determinist" means that, in any specific step of the algorithm, it cannot be established unequivocally established the next step should be. As in the game of chess: given one move of adversary, there is not at the moment an algorithm that can, a priori, determine in a reasonable time what the next move should be.

Ulterior problems, defined as NP-complete, are set in such a way that, if a problem in polynomial time is resolved, then all the group is resoluble. Among these problems the famous problem of the store clerk traveller who must visit a certain number of cities, without retracing his route, in the minimal possible distance.

In summary, the algorithms can be classified as:

• P polynomials: (for example, multiplication)

• NP non-determinsitic polynomial: (for example, factorization)

• NP complete: subclasses of those NP in which all the group are tractable (as an example, the problem of the store clerk traveller).

Although the classes of NP type are not the most complex, they contain however some intermediate problems which are,, at the moment, of greater interest. Among these, for instance, the problem of the factorization of a number is intimately connected with the possibility of decrypting a cryptography system, like the system RSA129 that uses keys constituted from 128 ciphers. It has been estimated that, in 1994, the factorization of a number of 128 ciphers required 5000 MIPS-YEARS (MIPS: million instructions per second), And it is just in the area of similar problems that the quantum computer enters the game. It has recently been discovered, as an example, than just the factorization in first factors of great numbers can be performed with an ideal quantum computer, using superimposition and entanglement, can solve, say, the algorithm of Shor (devised by Peter Shor in 1994). The algorithm of Shor is mathematically simple enough and demands modest quantum hardware, at least for small numbers.

Another problem for which the employment of quantum properties seems to open promising horizons relates to the solution of the so-called problem of the courier in the cryptographic systems. This problem is relative to the fact that any protected cryptographic transmission includes the unavoidable employment of a courier for the transport of the key. The courier is the weak point of the whole system (he/she can "betray", or, can be seized and forced to betray the key).

Nor do I think it can be helpful to suggest that the two partners in transmission can meet once to exchange the keys for all possible connections, because, for obvious security reasons, it is advisable to change the key at every connection. Therefore, for the two partners, if they want to communicate while each remains in his/her own base of work, there is no choice but to entrust one's message to a courier.

Cryptographic systems have remarkable similarities to a safe box, in which two security aspects can be described:

• the physical security, represented by the robustness of the system against thefts carried out with physical means (instruments of varied kind, thermal nozzle etc.).The physical security corresponds to the problem of the courier in a cryptographic system of transmission.

• the logical security, represented by the complexity of the opening key. The logical security corresponds to the problem of constructing algorithms which are sufficiently complex as to not be easily penetrated.

It is possible to demonstrate that intrinsically protected cryptographic messages can be obtained where, at every session, keys realized with random sequences of data are used, which a hostile cryptanalyst cannot work on. A cryptographic technique using a quantum procedure in order to realize exchange of keys produces absolute water tightness.

The physical reliability of devices for QC is strongly conditioned by the famous phenomenon of "quantum de-coherence", which is an unavoidable effect of interchange between a quantum system in which it is dipped.

The exciting effect of the superimposition of states with the consequent possibility of that it has been called quantum parallelism, faces a serious difficulty from the phenomenon of de-coherence. However, much progress in this direction has been made out and there is the now the possibility that the problem of de-coherence can be solved.

The maximum limit of scaling seems at this time to be about 50 qubits. And above all one does not know if a quantum program can be executed for the time necessary without incurring the phenomenon of the de-coherence. One of the more complex problems to resolve is how to prevent the interference of several calculations from being reflected in the macroscopic world. In fact, if a group of atoms or molecules is subordinate to a phenomenon of interference and interacts at the same time with the macroscopic environment, one is quite likely to find interference with measurements that relate only to atoms of the original group that therefore prevents any useful quantum calculation.

It is not possible at the present moment to formulate forecasts on the effective technical ability to construct a quantum computer able, for example, to decode in factors a first number at least 10 ciphers. There are at least three types of problems that are necessary to resolve.

In the first place, the maintenance of the state of quantum superimposition of several elements, and therefore an effective isolation of the quantum circuits from the macroscopic world that encircles them. In the second place, the management of the errors which however appear in a such delicate circuital complex. Finally, the constructive wisdom necessary in order to realize the calculational functions that, through superimposition, entanglement and interference, concur to create answers from the questions and to correlate the former to the latter.

The quantum computer would allow us, finally, to understand better not only the reality of the subatomic world but also the real meaning of computation, perhaps, and its role in the world.

The advent of "pocket" quantum computers does not seem imminent and not even interesting. The QC is not placed as competitive technology with the current computer (greater economy, more reduced dimensions ecc.), but rather in terms of allowing the solution of problems which the current technique are clearly insoluble.

The first steps will surely be undertaken in the direction of machines specialized in the solution of particularly arduous problems, with important impacts on the theorist-practical plan, that are not soluble, or hardly soluble, with the traditional classic techniques.

On the other hand, the founder of the mythical Digital (computer company ) the fifty years ago foresaw a market of hundred computers, at most, in all the world; therefore forecasting of the technological future is a hopeless enterprise.

The road to cover is enormously complex and it is not even sure that is really runneable. But even if in the end the quantum computer turns out to be as large as a building and demands hundred of specialists for programming and management, and cost hundredss of millions of euros, or still more, it could reveal a formidable instrument of calculation. 

What does it mean to assert that the state of a particle is a set of possible states? The photon that affects the glass passes or? An electron is here or there? In the quantum world the electron is here and there, but with various probabilities of being here and there. After a measure it can only be said if it is here.

However if it is attempted to measure a physical quantity of a system, the wave function of the system collapses and a precise value for a quantity is obtained that before was simply one of the many possibilities.

It is just the observation that leads to the "choice" of that particular value between all those possible ones. What causes the collapse of a wave function? The answer to this question is very complex but it can be answered, to a close approximation, that it is the interference between the quantum world and the macroscopic world.

The surprises from the discoveries of quantum physics are great that Heisenberg was led to observe that, in order to understand quantum physics, it is necessary to leave behind the certainties of classic physics, to which every being human is unavoidably attached, and that classic physics are no more than the description in rigorous mathematic terms of the daily experience of the physical world, necessarily based on macroscopic objects.

Following from the consideration that spin (the quantum entity that does not have equivalent in classic physics) is a conservative physical quantity, a quantum system is seen as constituted from two protons, strictly coupled and with null total spin. This situation corresponds to having the spin of two protons, measured along an assigned direction, oriented in opposite senses, that is, if a proton has spin +1/2 along a direction, the other will necessarily have spin -1/2 along the same direction.

If now one imagines that the two protons move indefinitely apart from one other until reaching an enormous separation (even very many light years, if it is the case!) it must be admitted, for the mentioned conservation, than the relation of antiparallelism of the spin remains conserved.

Therefore, where the spin measure of one of two particles is carried out along an assigned direction, forcing it into a determined state, necessarily also the far particle will be forced immediately in a determined state of its angular moment so as to conserve, along the same direction, the relation of antiparallelism of departure. In order to indicate this interdependence between particles in the Anglo-Saxon world the expression "Entanglement" has come into use.

This instantaneous action at a distance has been for along time considered paradoxical, until J.Bell demonstrated that the strange effect, even if apparently paradoxical, effectively is verified in nature.

This paradox on examination was thought to threaten the conclusions of theoretical physics: it was argued that possibility of having an effect at a distance in a null time violates the so-called principle of locality. Indeed, the cited paradox dose not infringe the locality principle, in that the result of the first measurement is as random as that of the second measurement (on the proton far away), is not compatible with the described experience of transmitting information between the two ends and, therefore, of producing an effect at a meaningful distance.

A quantum system evolves, according to an equation discovered by the physicist Schrödinger, until a measure is performed, then the system collapses into one of its possible states. The equation has the property that the linear combination of its solutions is still one of its solutions, consequently if the system starts in a superimposition of states, it will evolve into a block of all the superimposition of states.

Now consider the qubit: the qubit is considered homologous to the bit, that is the contained information in a quantum system of two states, like the spin of an electron. Where the electron is not in a defined state, but in superimposition of states 0(Spin "on") and 1(Spin "down"), in case checks to the state 0(Spin "on") the binary value "0" and to the state 1 (Spin "down")the binary value "1", the conclusion will be that the system electron is in a state representing the superimposition of" 0" and "1"- unimaginable in a classic world!

The superimposition, entanglement and interference are the three pillars to the base of the operation of the quantum computer.

According to the quantum mechanics the spin can be in a state of superimposition, that is in any combination of the two directions, as an example 30% clockwise and counter-clockwise 70%. The entire system is, therefore, an incredibly complex aggregate of superimpositions of all the possible combinations of spin for every particle. The evolution of a similar system, described from a complex probabilistic wave function, even today is an intractable problem, in any supercomputer. Image having an atom that has a single electron in the last occupied orbit. 

This electron can be moved, that is "excited", in a more external orbit by illuminating it with a light of a determined frequency and duration. The electron makes therefore a quantum jump to a more elevated energy. If such state is sufficiently stable it will be used, with a lower state of energy, in order to represent respective numbers 0 and 1.

If "an excited" atom receives a hit from a further impulse of light, similar to the previous one, the electron returns to the state of lower energy emitting a photon. 

But what happens if the duration of the first impulse of hard light is half of the time necessary in order commute the state of the electron? The answer is amazing for the logic to which we are accustomed: the electron will simultaneously be found in both the orbits. The electron will be then in a "superimposition" of the two states, fundamental and excited. 

A qubit is a "superimposition" of 0 and 1 and can be defined from the mathematical notation to |0> +b |1>, meaning with that, if measured, it could be 0 with probability a and 1 with probability b, being a and b complex numbers. For simplicity, without wanting to complicate matters, the mathematical nature of the states represents to you from the symbol |>, however one should remember that such symbol represents a vector, for its oriented nature. The state |1> +|0> is various from the state |0 >+|1>.

But how can the values stored in a qubit be modified? In other words, which type of operators can be used in order to modify the content of one or more qubit? The question is more general still.

In the quantum world it has possible to invert the content of a qubit. The impulse of light of opportune duration is equivalent to all the effects to an operator NOT. But illuminating the atom for half time it obtains a superimposition of states. A complete impulse is equivalent, therefore, to operator NOT. But what is equivalent to one of half duration ? To the operating square root of NOT.

Beyond the operator NOT other applicable types of operators exist in quantum mechanics,. Here is where finally the principle of Entanglement enters the game. If two qubits are both in the superimposition of 0 and 1 they are defined as Entangled if the result of the measurement of one of them is always correlated with the result of the value of the other qubit.

Entanglement, together with Superimposition, it is the key of the entire operation of the quantum computer. Without Entanglement, in fact, how could results be correlated with the input values? In order to illustrate this fundamental concept more clearly, a simple metaphor can be used. Imagine having a set of questions; for example, the multiplication of various couples of many great numbers, and distributing such multiplications between several persons. Every person will transcribe the result on a piece of paper and will place it in a box. The box in this example represents the output registry of a qubit. To extract from the box a result on each occasion is equivalent "to collapsing" the registry of a qubit to a precise value after a measurement. But to which question does the correspond, that is which multiplication, if there is only a piece of paper with the result? In the quantum computer it is precisely the mechanism of Entanglement which associates each results with its respective question.

At the same time the principle of Interference acts so that if a piece of paper with a result is extracted at the same time all the others are destroyed. With the three fundamental mechanisms of Superimposition, of Entanglement and Interference it is possible to construct an entire circuital quantum logic, at least on a conceptual level, with which the extraordinary calculating ability of a quantum computer can be highlighted.

If now a registry constituted from two electrons is constructed, whose stable spins are four, correspondents to the four binary states (00,01,10,11), where the state of the registry is not a defined state, but in superimposition of states, the system "electron couple " (= the registry at two electrons) will be found in a state that represents the superimposition of the couple of states 00,01,10,11. Therefore, in a registry with two cells, all the four states can cohabit in state of superimposition. In the registry the symbols 00,01,10,11, are written and overlapped and can be extracted with an appropriate measurement.

An important conclusion follows: in order to record the four values in the classic theory it would be necessary to have four registries with two cells,; instead, in the quantum theory, the four values are included in a single registry with two cells! And proceeding in the construction, a registry with 1 cell can contain 2 1 values, a registry with 2 cells can contain 2 2 values, a registry with3 cells can contain 2 3 values... a registry with n cells will be able to contain 2 n values.

The second conclusion follows: if the quantum system "registry" is left to evolve, it will cause all the states in superimposition to evolve simultaneously, realizing a type of operation in parallel, termed quantum parallelism. If the evolution equation is chosen in such way to lead to the solution of a defined problem, it will be sufficient to let the system evolve towards the desired solution, to which it will proceed by itself, simultaneously estimating all the supplied data in superimposition. This technique can turn out to be enormously favourable in cases where the computer must be used in order to estimate a large series of data.

However, the probability of finding the correct number will be very low because in the registry the not-solutions will be in state of superimposition with the solution, rendering the intended operation difficult.

In order to solve the problem it will be necessary to find how the not-solutions can interfere so that they cancel themselves. Naturally quantum registries of appropriate sizes must be available and that constitutes a still unsolved technological problem with no easy solution.

However the procedure has been verified for the decomposition of a small number (15 = 5 x 3), having demonstrated that the operation is possible.

The technology of the micro fabrication and the development of the materials for microelectronics have reached and will continue to grow to a progressive level of impressive, exponential miniaturization of the electronic components of computers.

Quantum effects cannot not be a factor if accurate operation of microchips is required, when these are used in devices for manipulating information.

It will also be possible to compute with molecular devices, thanks to miniaturization in due course, but these will not be quantum computers. In fact, quantum computation, is very different. Beyond energy there is another property of physics, at first glance so much more rarified that it would be said to belong rather to the realm of metaphysics, that has universal validity, which can be expressed in totally different ways, independent from its physical support: Information. Like the observable objects of physics, Information must be contained in forms that can be o fgreat variety; spoken words are tuned from the variations of air pressure, written words from the disposition of molecules of ink on paper, thoughts even correspond to particular configurations of the neurons, and above all, as with the observable data of physics, raw Information comes from solid transformations.

Information behaves in some ways like a physical entity, in that it can be conserved, be transformed, be measured and dissipated.

Nowadays,as we all know, the computer is an excellent source of information.

The facility with which the information can be manipulated automatically is derives simply from its universality, from the fact that it can be expressed in various ways without losing its essential nature and that, as in physics, more complex transformations can be realized with many simple operations.

There is no Information without a physical bearer, but Information is essentially independent from how it is expressed physically and can be freely transferred from one form to another: so Information is a natural candidate for a fundamental role in physics, exactly like energy and momentum.

Historically the great role of fundamntal physics has been to discover the fundamental constituents of matter and the laws that describe and govern their interactions and their dynamics. Now IT begins to emerge as an important and equally fundamental program to discover in which ways the nature allows or forbids Information to be expressed, stored, manipulated and transmitted.

The ambitious program to reconsider the fundamental principles of physics from the point of view of the theory of Information is still in its infancy; however it promises to bear important fruits: the concepts and the methods of Information and quantum computation are the first among these.

From the time of Turing, essentially no substantial change has taken place in the idea of what a Computer is and how it works; until now, quantum mechanics has not opened the possibility of a change of paradigm.

In effect, the Aristotelian logic of the Turing machine is badly adapted to the human rationality (are True and False sufficient concepts?). Perhaps another possible logic exists.

Quantum mechanics is a mathematical structure set up in order to describe Nature that, at least in principle, compares any physical system from the corresponding classical picture with an outline made from of a great variety of paradigms : variable dynamics are associated with a series of states in which the vectors can have infinite complex members, the wave functions. Only after difficult reinterpretation of observed concepts and of the meaning of such weird properties of operators, can the classic ones be put into an analogous variable relation.

It is interesting to notice how the more important properties of the quantum theory are not in the details of the equations of motion and of dynamics that they generate but just in the fact that the quantization of a classical physical system with N degrees of freedom generates a quantum system whose space of the states has a volume that exponentially grows with N; so the quantum theory leads to an enormously large,complex, combination co of possible dynamic structures. The idea that Information can be stored in microscopic states is for the physicists an unprecedented challenge, in opening vast perspectives in the use of that same matter, in its fundamental structure, in order to make calculations.

The class of problems that can efficiently be resolved by quantum computers are called BQP "bounded error, quantum, polynomial time". Quantum computers substantially execute randomized algorithms only a. One says that a quantum computer resolves a problem if for every request the answer will be correct with high probability. If the solution is found in "short time" the problem belongs to the BQP class. Although the quantum computers are often faster than classic computers, they cannot resolve all the problems. One Turing machine instead can simulate a quantum computer.

List of requirement that a quantum computer must satisfy:

Practical difficulties are numerous in constructing a quantum computer and those existing, "ad hoc" for specific problems resolve banal problems only.

The candidates technologies in order to make quantum computers:

Real quantum computers do not exist but emulators exist. It is possible to download one here.