No-cloning and quantum neural networks

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:

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:

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.

One thought on “No-cloning and quantum neural networks”

1. DOT says:

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.

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.

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
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
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