Our paper on Input Redundancy for Parameterized Quantum Circuits was just published by Frontiers in Physics. A good excuse to talk about the no-cloning theorem and its consequence for quantum neural networks.
The No-Cloning theorem states that quantum information cannot be duplicated: There is no mechanism which takes the quantum state of, say, a qubit and copies (i.e., duplicates) it to another qubit:
|𝛙⟩ ↦ |𝛙⟩ ⊗ |𝛙⟩ — no way!!
It is really a simple consequence of the fact that time evolution of quantum states is linear, and the mapping above isn’t.
Anybody who has ever written computer code should now be puzzled how to implement even simple algorithms for quantum computers, because in classical computing, copying of information is a basic primitive. Writing code without using “y=x“? Copying can be done on a quantum computer as long as the information that’s being copied is classical. For example, the following defines a valid quantum operation which duplicates the information in a qubit, provided that it is classical, i.e., just 0 or 1:
|0⟩ ↦ |0⟩ ⊗ |0⟩ and |1⟩ ↦ |1⟩ ⊗ |1⟩
But what’s the point having your quantum computer work on classical information — classical computers are way better at that. Quantum information is processed based on a new set of primitives which doesn’t include copying (and has very little to do with how classical information is processed).
Another primitive of computing where information is cloned is fan-out, which indicates that the output of one node is the input of several others. Example: In artificial neural networks, the output signal of one neuron is the input signal of several others. On quantum computers, fan-out isn’t possible: So-called Quantum Neural Networks (QNN) operate fundamentally different from classical artificial neural networks, without duplicating information.
In our paper, we studied what no-cloning means for the classical input that is fed into a QNN. The concept of “input” needs some explanation.
The temptation of QNNs (or quantum computing in general) is that with n qubits, you can represent a 2n-vector of complex amplitudes, i.e., a 2n+1-2 dimensional data point. If you could make that work, Big Data would get really small. According to this Forbes article, humanity produces 2.5 quintillion (1018) bytes of data per day. As the universe is roughly 5.125 trillion days old (~ 14 billion years), 5.125·1030 should be a generous upper bound on the number of bytes that have been produced so far. That fits conveniently into a quantum computer with 101 qubits, which is within reach of today’s technology. Oops.
Of course, that’s a bullshit calculation, but you see the temptation: If you encode classical data as the amplitudes of a quantum state, you might be able to process large datasets with modest quantum resources. (Don’t let the obvious naivité of the idea fool you: It plays a role in some “serious” quantum algorithms, e.g., in quantum numerical linear algebra and the quantum Fourier transform. The latter drives Shor’s algorithm for factoring.)
In our research we had the idea that if classical information is encoded as amplitudes of a quantum state, then the no-cloning principle suggests that you have to feed your input data into the QNN several times. What we asked was: How often do you have to feed your input data in, if you want your QNN to represent a function of a certain complexity? Using Fourier analysis and complex analysis techniques, we were able to give good lower bounds.
While working on the proofs of the lower bounds, we also realized that the “right” way to encode input was what we called variational input encoding. This realization allowed us to make concrete design proposals for QNNs. Andrew Lei, a master’s student who graduated this summer, compared variational input encoding to some other known input encodings in practice in this thesis Quantum Computing Techniques for Machine Learning, and — no surprise — found variational input encoding to be superior.