Figure 1: Controlled NOT Gate
This test is still quite easy, because Bob just needs one logic gate to solve this perfectly: the Controlled NOT (CNOT) gate.
| A | B | C | D |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
With the input B = 0 this is often referred to as a FANOUT gate, and with A = 1 it is a NOT gate.
Bob takes Alices bit, and a second bit prepared in the state 0. Alice's bit is fed into the A-input, and Bob's second bit is fed into the B-input of the CNOT gate. The two output bits will now be in the same state as Alice's initial bit.
The answer is that Bob acquires 1 bit of information. By passing the two bits through the CNOT gate, A is in the initial state, but D is always in state 0. Although Bob has no information about the state Alice sent, he has an absolute certainty about the state of D. For the second case, Bob performs a NOT upon B, before passing it through the CNOT.
By informing Bob of the correlation between A and B, Alice has reduced the number of the possible states (or Bob's uncertainty) by 1 bit. Bob converts this correlation information into a certainty about the state of one of the bits ('using up' the correlation). Bob can switch between these states but always has exactly 1 bit of information about the joint system. The three states are ''informationally equivalent''. Creating duplicate bits, or flipping those duplicate bits, cannot be used to increase or decrease the information available. This is why Bob found the tests so easy: Alice was not requiring Bob to supply any more information back to her, than she had sent to him in the first place.
Now Alice and Bob try to do the same thing, but with quantum bits. A quantum bit (or qbit) is a two dimensional Hilbert space, with basis states |0 > and |1 > , The general state of qbit is:
|
|
The inner product of two qbits is
|
Now we need the logical operations Alice and Bob can perform upon qbits, and it turns out that a single gate is sufficient to represent all of them - the quantum controlled-not[D94 ].
|
How much information is there in a single qbit? There is a lot more possibilities for the qbit, than for the bit. Surely, this gives Alice a much wider range of signals she can send Bob.
However Bob has a problem. Alice sends Bob a single, unknown qbit in a box. It could be pointing anywhere on the Bloch sphere. When receiving a classical bit, Bob can simply open the box, find out what it is, and gain one bit of information. However, for a qbit, Bob must make a measurement, along a particular axis. If he chooses the conventional axis, he gets the probabilities
|
Although a large number of identically prepared qbits will eventually yield up the value of q, Bob doesn't get any information about f and Alice could be sending qbits pointing in different directions. As the measurement described has only two outcomes, it turns out Bob can get, at most, one classical bit of information from the transmitted qbit. With an infinite amount of qbits, Bob can find q exactly, but this is the same as the infinite amount of bits necessary to specify a continuous parameter. The average information conveyed by each qbit is still one bit.[ S95 ][JS94 ][H73 ]
This suggests that there is no difference, in information content, between the classical and quantum bits. However, if we look again at the trivial tests Alice set, we find Bob has a much harder task. We will judge Bob's success at playing the game by a FIDELITY test. If Bob is supposed to produce a qbit in the state |u > = a |1 > +b | 0 > , Alice will measure the state he actually produces in the |u > ,| - u > basis, and the fidelity is the probability of Bob's qbit passing the test. In order to test a given strategy, we average this over all the possible states Alice could have chosen.
Bob has a number of strategies.
Bob is feeling bored with this silly game. He throws Alice's bit away and sends her two bits, each of which he prepares in some random, but identical state, |n¢ > = a¢ |1 > +b¢ |0 > . When Alice measures Bob's qbits, the probability of passing is cos2( [(q)/2]) where q is the angle between the Alice's and Bob's directions. The mean fidelity of each bit is F = 1/2 and the joint fidelity (the probability of getting both right) FJ = 1/3. While random guesswork is not a good solution it gives us a baseline to measure the success of other methods.
Bob measures the bit in some basis (for convenience, we use |1 > ,|0 > ), and sends back two bits in the direction the measurement gives. This gives a density matrix r = | a| 2 |11 > < 11|+| b|2|00 > < 00 | and average fidelities F = 2/3, FJ = 1/2
Bob thinks the problem might be because he is opening the box to measure the qbit, and this disturbs the quantum system. So he uses in logic gates (FANOUT) to copy the qbit, without opening the box. This produced a perfect solution with classical bits. However, with qbits, the result is F = 2/3, FJ = 1/2 and is no better than ''measure and copy''! What went wrong?
The answer is that FANOUT fails to copy the qbit - instead it creates an entangled state between the output bits:
|
|
Can we build a quantum FANOUT? If we take an initial, unknown qbit, and a auxiliary system, prepared in a known state, does there exist any unitary operation of the form:
|
|
|
However, it is possible to build imperfect cloning machines, that produce a fidelity better than simply 'measure and copy'.[BH96 ][GM97 ][BBHB97 ][BDEFMS98 ] An example of an optimal quantum cloning, in which the fidelity of the output is independant of the input state, is given by the following unitary operation:
|
What of Alice's second test? What if Bob has to produce two qbits, but in opposite directions?
Bob has the same strategies available to him. If he measures Alice's bit, and sends back opposite qbits |10 > or |01 > , he gets the same fidelity of as 'measure and copy' for producing the same qbits. If he runs the qbit through a FANOUT and a NOT gate, he get the fidelity of 'FANOUT' for same qbits.
What if he uses an optimal cloner and NOT? Surprisingly, our joint fidelity is worse and our opposite bit is terrible!
Fs = 5/6, Fo = 7/12, Fj = 2/3
The reason for this failure is that our NOT gate is failing to work in the way we desired:
|
|
Still, perhaps there is an imperfect OPP, in the same manner that there is an imperfect CLONE? It turns out the best that can be done is to build an anti-cloning machine, that takes an input qbit | n > and attempts to make output qbits | n > |-n > , succeeding with fidelity F = 2/3 , joint fidelity FJ = 5/8. [ GP99 ][BHW99 ][SH00 ]
Now this is particularly interesting - not only is Bob failing Alice's test, but trying to produce an opposite second bit is failing worse than a same second bit. Somehow it seems opposite is not informationally equivalent to same? Rather than examine proofs of the no-cloning and no-spinflipping theorems, let us look at the states we are trying to produce - the duplicate qbits.
Suppose Alice sends Bob a qbit prepared in a state unknown to Bob. Bob's uncertainty is at a maximum, as he has no information on the state of the bit. Now Alice sends Bob a second qbit, also unknown, but prepared in the same state as the first qbit. How much more information does Bob possess?
In the classical case, we saw that the answer was one bit. However, that was clearly related to the fact that we could run both bits through the FANOUT gate, and put one of them into a definite state. This is clearly not possible for qbits: if it were, we could simply reverse the process, and clone a qbit[].
If we take an ensemble of qbits, in different states eg.
|
|
|
|
|
|
For two qbits prepared in the same state | n,n > , the density matrix, when |n > is integrated over the Bloch sphere, is:
|
|
|u+ > = [1/(Ö 2)]( |u,-u > + |-u,u > ) .
This is not complete uncertainty. A total lack of knowledge is represented by
|
What if they are in opposite states - how much information have we gained? Two qbits in unknown, opposite states have a averaged density matix of
|
|
|
This clearly is a property of non-orthogonality in the quantum measurement process - even if we are sure the states were prepared in same (or opposite states), we cannot be sure they will both pass/fail (or the opposite) if the measurement is in a different basis. The essential feature of this is the non-orthogonality of the states the qbits may have been prepared in. If we are told that the qbits are prepared in a particular basis, then we can simply switch our logic gates to operate on that basis, and all our results of classical logic apply.
Although the separation between the two cases is guaranteed by the no-spin flip theorem, this does not explain why oppositeness conveys so much less information than sameness.
The wavefunctions and density matrices above, were expressed in the basis
|
|
|
|
|
|
||||||
|
|
|
|
|
|
In [`(r( |n,n > ))] , the probability of finding the state F3 is zero, while for [`( r(|n,-n > ))], it is one half.
Using the notation
|
|
|
|
|
|
||||||
|
|
|
|
|
|
we can construct the F basis from a superposition of opposite states:
|
|
The space of the two qbits SU(2)×SU(2) has two invariant subspaces, under global rotations: a symmetric subspace, of dimension 3, and an anti-symmetric subspace, of dimension 1. 'Sameness' means that the qbits can only be found within the symmetric subspace, and are evenly distributed throughout it. While in the classical case, the correlation information restricts the bits to a two dimensional subspace (and therefore represents an ignorance of log(2) bits) in the quantum case the restricted subspace is 3 dimensional, and the ignorance is log(3) bits. The opposite qbits are distributed throughout the entire state space - but they are likely to be found in the antisymmetric subspace, so 'oppositeness' does give some correlation information.
What is remarkable, however, is that these differences can only appear when one looks in an entangled basis, even though the qbits themselves are always prepared in product states! The measurement is of a joint property of the qbits - we cannot relabel the parts of the apparatus that apply only to the second particle, because there are no such parts. If we were to 'flip' the second qbit in the 'opposite state' expansion of the of the F basis, the result would no longer be an orthonormal basis, and does not correspond to a valid measurement (see also [M00 ]). This strange phenomena - entangled state measurements yielding more information than any combination of local measurements, even when made on ensembles of product states - has been dubbed 'non-locality without entanglement' [ BDFMRSSW99 ]
The theory of reversible computation was developed following the discovery of Landauer's principle[L61 ], that only logically irreversible operations implied an irretrievable loss of energy (prior to that, it was thought that each logical operation involved a dissipation of kTln(2) per bit). The amount of lost energy is directly proportional to the Shannon measure of the information that is erased.
It is often defined as a requirement to 'do work' to perform the erasure. This is not strictly accurate. It requires an investment of kTln(2) free energy, per bit of information that is stored. At any time in the computation, any bit that is in a known state can have this free energy recovered. A known state is one that is in a particular value, regardless of the choice of input state, (we may extend this to include always in the same state as an initial input state). When we examine a computational network, given the program, and the input state, we can recover all the free energy from the bits that are known. Other bits may be in determinate states, well defined functions of the input. It may be argued that these are, therefore, 'known' but, as these states are non-trivially dependant upon the input state (eg. (A OR NOT B) AND (C XOR D)), to extract the energy requires one to find the value of the bit from the input state ie. to recapitulate the calculation on a second system, which requires an investment of an equivalent amount of free energy - so no gain is made in terms of recoverable energy. The objective of reversible computing is to reduce the amount of the free energy invested into the calculation that cannot be recovered at the end without losing the results of the computation.
A reversible calculation may be defined as one which operates, upon an input state i and an auxiliary system, prepared in an initial state Aux0 , to produce an output from the calculation O(i), and some additional 'junk' information Aux(i):
|
|
However, Aux(i) is not generally known, being non-trivially dependant upon the input, i, and so represents free energy that cannot be recovered. A general procedure for discovering the complementary calculation F ¢ can be given like this: take all the logical operations performed in F, and reverse their operation and order. As long as all the logical operations in F are reversible logic gates, this is possible. It is known that the reversible Fredkin-Toffoli gates are capable of providing all classical logical operations. So it is always possible to make a computation reversible. However, this is not immediately very useful: although we could recover the energy by reversing the computation, we lose the output O(i) in doing so.
Bennett[B73 ][B82 ] showed that a better solution was to find a different reverse calculation F"
|
Straight away, we should notice a problem! The universal FANOUT gate does not exist for a quantum computation.
Clearly, in the case where the output states from a quantum computer are in a known orthogonal set, then the quantum computation can be made tidy. In fact, for other reasons, having orthogonal output states was initially taken as a requirement on a quantum computer, as it was deemed necessary for reading out the output. This was suggestive not of a general quantum computation, but of limited quantum algorithmic boxes: each connected by classical communication. However, developments in quantum information theory have suggested that distributed quantum information may be desirable - in particular, a more general conception of quantum computation may be required which takes inputs from different sources, and/or at different times. In Figure 4 we see an example of this - Alice performs some quantum computation, and stores the result of it in a 'quantum data warehouse'. At some later time, Bob takes part of these results as an input into his own computation.
We are going to take our definition of a quantum computation as: 2
|
If this model of computation is classical, then each time data is sent to the central database, the local user can FANOUT the data before sending it, and tidy up their computer as they go along. The only energy commitment is: total input, plus stored data. The difference between connected classical algorithmic boxes and a single classical computation is a trivial distinction, as the computation may be tidied along the way.
Considering a general quantum operation, unitarity requires that the inner products between different input states and between the corresponding output states is unchanged by the computation. Reversibility must always hold.
|
The output states are orthogonal set:
|
The input states are orthogonal set < i| j > = dij, but the output states are not. To satisfy unitarity, the auxiliary output states must be orthogonal.
|
One obvious method is to examine the resulting auxiliary output states, construct a unitary operator from
|
The input states are a non-orthogonal set. This corresponds to Bob's position in the quantum distribution network of Figure 5.
If we look at the requirements for a tidy computation, this leads to:
|
|
It should be clear: this does NOT mean useful, reversible quantum computations of the form
|
We have examined the notion of 'sameness' and 'oppositeness' when applied to quantum information and found that the 'informational equivalence' of these in the classical case no longer hold. Quantum information cannot be copied or duplicated, in the manner of classical information.
This has a surprising consequence for computation. The flow of information in a classical computation can be broken down into separate algorithms, with these algorithms passing classical information between them. Such algorithms can be reversibly, and tidily, implemented. If the overall calculation requires input data in separate places and times, it can easily be broken down into separate algorithms at each place and time, with classical communications between them. This is only because such classical information can be duplicated in an 'informationally equivalent' manner.
Existing quantum algorithms have been designed on the basis of replacing similar classical algorithms. They therefore take a set of classical inputs, at one place and time, and produce a set of classical outputs, and so can be implemented in a tidy manner. However, each quantum algorithm itself cannot be broken down into sub-algorithms.
A more generalised conception of the flow of information in a quantum system appears necessary. Information enters and is shared at separate times and places, and cannot necessarily be processed by tidy sub-algorithms, as the information exchanged is not necessarily classical in nature. Even where a tidying procedure can exist, it is not clear that a general and/or efficient program for implementing this procedure is available.
''Oppositeness'' and ''Sameness'' are well defined, conceptually simple, relationships between qbits, yet there are no physical systems that can implement these as operations such as OPP and CLONE. We must therefore be very careful before assuming which logical ideas can still be relied upon when trying to understand the nature of information in quantum processess.
1 In classical logic, there are three input gates which cannot be built from reversible two input gates. These three input gates can be constructed from two-input quantum gates that are not equivalent to two input classical gates!
2 There is further complication when entanglement enters the problem. When part of an entangled state is transmitted, the loss of free energy is always greater than the entropy of the reduced density matrix. The minimum loss of free energy requires knowledge of an accurate representation of the resulting density matrix - which may not be possible without explicitly calculating the output states.
3
It is interesting to note that the 'no-cloning' theorem is a special
case of this.