No-gos, the quantum no-nos
Welcome to Introduction to Quantum Computing. I am your guide, Associate Professor Chris Ferrie, a researcher in the UTS Centre for Quantum Software and Information. This is Lecture 4. It would probably be a good idea to have read the previous Lectures before continuing.
What did you learn last week?
Last week you completed your basic training. You now know about quantum information, how to write it, how to read it, and how to dial it up to 11 with entanglement. Entangled states were those that could not be written as product states (in any basis!). With multiqubit states and gates, you have all the tools you need to start creating quantum algorithms and proving things!What will you learn this week?
Before you are set loose on the quantum world, know that things are different in ways beyond just possessing more possibilities. Quantum information is severely restricted. The so-called "no-go" theorems show that things like copying and deleting quantum data is impossible!What will you be able to do at the end of this week 2?
At the end of this module, you should be able to answer these questions:
Can qubits store an infinite amount of information?
Can quantum information be copied?
Can quantum information be deleted?
What else can’t I do with quantum data?
PHENOMENAL QUANTUM POWERS! Itty-bitty information space!
It takes 2ⁿ complex numbers to specify a quantum state of n qubits. Does that mean that real, physical manifestations of qubits store an exponential amount of information? Let’s phrase this in another way. You may be familiar with data compression. If not, it’s basically what MP3, JPEG, ZIP, or many other “file formats” do to your data. The “raw data” — in the case of JPEG, for example — is the exact pixel-by-pixel image which is converted to a smaller amount of data through encoding. The encoding can reduce the number of bits required to store and transmit the image by a factor 10 without the human eye noticing the difference. However, information is lost — and a computer would notice.
A compression algorithm that loses no information is also possible. This may seem counterintuitive, but imagine “unzipping” a file and it only working 75% of the time! Intuition for how it works boils down to simple repetition. Take the following phrase for example, which has 70 characters taking 70 bytes of data.
I have four qubits: qubit one, qubit two, qubit three, and qubit four.
If I “zip” this sentence, I get the following.
eJzzVMhILEtVSMsvLVIoLE3KLCm2gtAK+XmpOlBmSXk+nJlRlAoUT8xLgQqAdOoBAHKvGOU=
This only uses 53 bytes to represent — 132% compression without losing a single bit! But not so fast. What if I wanted to compress this randomly generated string?
ioqjbM2ZZWDV8XWmh8pKU5d2wUWEqeAemQc4ieEJF0xOqpF7mijzkeBDrIpcQVklaSx6LV
It turns out that “zipping” this 70 byte string results in a new string with 78 bytes! Lossless compression only works when there is repetition. Can quantum help? Can you take those 70 bytes and encode them as decimal digits in the coefficients of a single qubit even?
No, you can’t, and the reason comes down to measurement — what we called reading quantum data. Remember that no matter what the state of the qubit is, and no matter what gates you apply to it, the results of reading the quantum data is either |0⟩ or |1⟩. That’s one of two possibilities, or 1 bit! For two qubits, the possible results of measurement are |00⟩, |01⟩, |10⟩, or |11⟩ — 2 bits. And so on.
The formal proof is due to Alexander Holevo and requires tools beyond the scope of this subject to show here. The punchline is simple to state though — no matter how many bits you try to cram into n qubits, the accessible information is limited to n classical bits. Exponential promises, linear capacity.
QC LOAD LETTER
How did I make this lecture? Well, I definitely started with a CTRL-C followed by a CTRL-P. Since the header is the same for every lecture, I can simply copy-and-paste it rather than type it out again. In the physical world, photocopiers achieve a similar task. Both of these are more complicated versions of this digital circuit.
And how about quantum data — can we copy that as well? What would that look like?
This looks kind of familiar from last week. Recall the CNOT gate, which can be thought of as applying an X gate on the second qubit if the first is in the |1⟩ state. Explicitly CNOT|10⟩ = |11⟩, and CNOT|00⟩ = |00⟩. This looks like it does the trick, right?
The problem occurs when we consider not just basis states but also superposition states. Consider the most general state |𝜓⟩ = 𝛼|0⟩ + 𝛽|1⟩. If we apply a CNOT to this we get CNOT|𝜓0⟩ = 𝛼|00⟩ + 𝛽|11⟩, which is definitely not equal to |𝜓𝜓⟩.
Of course, we can make it work if 𝛼 = 0 or 𝛽 = 0 — but then we are back to copying only |0⟩ or |1⟩. So the CNOT doesn’t work. What about a different gate? There is a continuous infinity of 2-qubit unitary matrices after all!
If we call this hypothetical gate C, it must act as C|𝜓0⟩ = |𝜓𝜓⟩ and C|𝜙0⟩ = |𝜙𝜙⟩ for any two states |𝜓⟩ and |𝜙⟩. Now consider the inner product of these two states.
So it seems that, indeed, the only states you can copy are those for a basis — this is essentially just classical information. There are no quantum photocopiers!
Wrong to be forgotten
The “right to be forgotten” is the right to have your data removed from internet searches and other directories. While many argue about how to technically achieve this in the case of specific internet systems, it is in principle possible to delete data. The deletion circuit is almost the reverse of the copy circuit.
Here we demand that some parts of the memory remain intact. This seems all very simple and trivial. As a side note, it’s not. Any irreversible computation must consume energy. This is Landauer’s principle, and leads down a rabbit hole beyond the scope of these lectures. Interesting, it was this kind of thinking (what the physical limits are on computation) that led to quantum computing. If we make a similar demand for quantum data, it would look like this.
The delete circuit, D, must act as D|𝜓𝜔⟩ = |0𝜔⟩ and D|𝜙𝜔⟩ = |0𝜔⟩ for any two states |𝜓⟩ and |𝜙⟩. Playing the same game as before, we find.
So we can’t create a delete circuit that works for more than a single state! But perhaps this is too rigid a circuit. What if we allow other parts of the computer to potentially change. So we might be able to find a delete circuit that acts as this.
We can use linearity to see how it must act on any state |𝜓⟩ = 𝛼|0⟩ + 𝛽|1⟩.
So, it seems this circuit works. However, if those two garbage states are orthogonal, then the information can be retrieved with a single gate. Let’s check that.
This means that quantum data is now stored in other parts of the computer. It was never deleted! There is no quantum shredder either. What no-cloning and no-deleting point is a conservation of quantum information.
These are called no-go theorems. They are sets of contradictory requirements on quantum information which usually contain something trivial that can be done with classical bits. There is also no-signalling, no-hiding, and even no-programming. Geez, it seems like there is not much quantum information can achieve at all! But don’t worry, we will soon see some positive results about quantum information.
