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.)
Our research
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.
Meie artikkel („Parametriseeritud kvantahelate sisendi liiasus“) ilmus
äsja ajakirjas “Frontiers of Physics”. See on hea ettekääne, et
rääkida kloonimise võimatuse teoreemist ja selle tagajärgedest
kvantnärvivõrkudele.
Kloonimise võimatuse teoreem ütleb, et kvantinformatsiooni ei ole
võimalik kopeerida. Pole olemas mehhanismi, mille abil saaks võtta
kvantoleku, nt kvantbiti oleku, ja kopeerida (st teha identne koopia)
see teisele kvantbitile.
|𝛙⟩ ↦ |𝛙⟩ ⊗ |𝛙⟩ — pole võimalik!!
Selle põhjuseks on lihtne asjaolu, et kvantoleku evolutsioon ajas on
lineaarne, samas kui ĂĽlal toodud kujutis ei ole lineaarne.
IgaĂĽks, kes on kunagi programmeerinud, kĂĽsib nĂĽĂĽd, kuidas on
kvantarvutites võimalik kasutada isegi kõige lihtsamaid algoritme,
sest meie klassikalises arvutusparadigmas on informatsiooni
kopeerimine üks kõige olulisemaid primitiive. Kuidas kirjutada koodi,
kui ei saa kasutada „y=x“-i? Kvantarvutis on võimalik informatsiooni
kopeerida, kui kõne all olev informatsioon on klassikaline. Näiteks
järgnev jada defineerib kehtiva kvanttehte, millega kopeeritakse
kvantbitis olev info, eeldades, et see on klassikaline, st lihtsalt 0
või 1.
|0⟩ ↦ |0⟩ ⊗ |0⟩ ja |1⟩ ↦ |1⟩ ⊗ |1⟩
Aga miks peaks kvantarvutil töötlema klassikalist informatsiooni, kui
meie klassikalised arvutid on ses vallas palju paremad?
Kvantinformatsiooni töödeldakse uute primitiivsete tehete abil, mille
hulka ei kuulu kopeerimine (ja millel ei ole eriti pistmist
klassikalise andmetöötlusega).
Teine primitiivne tehe, mille abil informatsiooni kloonitakse, on
“fan-out”, mis tähendab sisuliselt, et ĂĽhe värati väljund on sisendiks
mitmele teisele väratile. Näiteks tehisnärvivõrkudes on ühe neuroni
väljastatav signaal sisendsignaaliks mitmele teisele neuronile.
Kvantarvutites ei ole “fan-out” võimalik. Nn kvantnärvivõrgud töötavad
klassikalistest tehisnärvivõrkudest fundamentaalselt teistmoodi ilma
informatsiooni kopeerimata.
Artiklis me uurisime, mida tähendab kloonimise võimatus klassikalise
sisendi jaoks, mis on sisendiks kvantnärvivõrkudele. Sisendi mõiste
vajab veidi selgitamist.
Üks kvantnärvivõrkude (või üldiselt kvantarvutuse) ahvatlusi on
selles, et soovitakse n-arvu kvantbittide abil esitada
2^n-dimensionaalse vektori kompleksamplituude, st ĂĽhte 2^(n + 1) – 2
dimensioonilist andmepunkti. Kui see oleks võmalik, muutuksid
suurandmed (Big Data) väga väikseks. Forbesi artikkel
(https://www.forbes.com/sites/bernardmarr/2018/05/21/how-much-data-do-we-create-every-day-the-mind-blowing-stats-everyone-should-read)
väidab, et inimkond toodab iga päev 2,5 kvintiljonit (10^18) baiti
andmeid. Kuna universum on umbes 5,125 triljonit päeva vana (u 14
miljardit aastat), peaks praeguseks olema toodetud umbes 5,125 Ă— 10^30
baiti andmeid. See mahub kenast ära 101 kvantbitiga kvantarvutisse,
mis on tänapäeva tehnoloogiaga täiesti võimalik. Oops.
See arvutuskäik on muidugi puhas jama, aga ehk annab see aimu
kiusatusest. Kui kodeerida klassikalised andmed kvantoleku amplituudi,
siis oleks võimalik töödelda suuri andmehulki väga väikse
kvantressurssi abil. (Ă„rge laske selle idee naiivsusel end eksitada;
see mängib rolli mõnedes „tõsisemates“ kvantalgoritmides, näiteks
kvantarvulises lineaaralgebras ja kvant-Fourier teisenduses. Viimane
on oluline element Shori faktoriseerimisalgoritmis.)
Meie uurimistöö idee seisnes idees, et kui klassikaline informatsioon
kodeeritaks kvantoleku amplituudina, peaks kloonimise võimatuse
põhimõttest lähtudes sisendandmeid kvantnärvivõrku sisestama mitu
korda. Küsisime järgmist: kui tihti peaks andmeid sisestama, kui
soovitakse, et kvantnärvivõrk väljendaks kindla keerukusega
funktsiooni? Fourier analĂĽĂĽsi ja kompleksanalĂĽĂĽsi tehnikat kasutades
leidsime rahuldavad alampiirid.
Alampiiride tõestamise kallal töötades mõistsime, et „õige“ viis
sisendi kodeerimiseks oli variatsiooniline sisendkodeering, nagu meie
seda kutsusime. See tõdemus võimaldas meil kvantnärvivõrkude
kavandamiseks konkreetseid ettepanekuid teha. Andrew Lei, magistrant,
kes sel suvel ĂĽlikooli lõpetas, võrdles oma magistritöös “Quantum
Computing Techniques for Machine Learning” („Kvantarvutusmeetodid
masinõppimiseks“) variatsioonilist sisendkodeeringut teiste tuntud
sisendkodeeringutega ja leidis — ootuspäraselt —, et
variatsiooniline sisendkodeering on etem.