1968 - 1980:
Stephen Wiesner ( Wiesner is a founder of quantum information theory and the inventor of quantum money) invents conjugate coding *(see below. (manuscript written while participating in the Columbia University student protests of April 1968 and eventually published in ACM SIGACT News 15(1):78–88))
Conjugate coding is a cryptographic tool introduced by Stephen Wiesner in the late 1960s. It is part of the two applications Wiesner described for quantum coding and a method for creating fraud-proof banking notes. The concept's application is proposed based on a method of transmitting multiple messages in such a way that reading one destroys the others. It is called quantum multiplexing, and it uses polarized photons in conjugate bases as "qubits" to pass information. His proposed Conjugate coding method also is a simple extension of a random number generator. Wiesner was significantly ahead of his time. At the time the initial concept of quantum cryptography developed, I will cover the topic in another post.
1970
James Park articulates the no-cloning theorem. In physics, the no-cloning theorem states that it is impossible to create an independent and identical copy of an arbitrary unknown quantum state, a statement which has profound implications in the field of quantum computing among others. The theorem is an evolution of the 1970 no-go theorem authored by James Park,[1] in which he demonstrates that a non-disturbing measurement scheme which is both simple and perfect cannot exist (the same result would be independently derived in 1982 by Wootters and Zurek[2] as well as Dieks[3] the same year). The aforementioned theorems do not preclude the state of one system becoming entangled with the state of another as cloning specifically refers to the creation of a separable state with identical factors. For example, one might use the controlled NOT gate and the Walsh–Hadamard gate to entangle two qubits without violating the no-cloning theorem as no well-defined state may be defined in terms of a subsystem of an entangled state. The no-cloning theorem (as generally understood) concerns only pure states whereas the generalized statement regarding mixed states is known as the no-broadcast theorem.
1973
Alexander Holevo publishes a paper showing that n qubits can carry more than n classical bits of information, but at most n classical bits are accessible (a result known as "Holevo's theorem" or "Holevo's bound").
In physics, in the area of quantum information theory, Holevo's theorem (sometimes called Holevo's bound, since it establishes an upper bound) is an important limitative theorem in quantum computing which was published by Alexander Holevo in 1973. According to the theorem, the amount of information accessible given a quantum state ho is limited by its "Holevo information":S( ho) -sum_{i}^{} p(i) S( ho_i) where S( ho)=-operatorname{tr} holog_2 ho is the von Neumann entropy, ho=sum_{i} p(i) ho_i and ho_i are the states used to encode the information under the prior distribution p(i).
In essence, it proves that "n" qubits can represent only up to "n" classical (non-quantum encoded) bits. This is surprising, for two reasons: quantum computing is so often more powerful than classical computing, that results which show it to be only as good or inferior to conventional techniques are unusual, and because it takes 2^n-1 complex numbers to encode the qubits which represent a mere "n" bits.
Charles H. Bennett shows that computation can be done reversibly.
Abstract:
The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible- its transition function lacks a single-valued inverse. Here it is shown that such machines may he made logically reversible at every step, while retaining their
simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, thereby avoiding the irreversible operation of erasure.
The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), thereby restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results
are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.
Download the document here (it is free)
Comments