# Mostreig de bosons

El mostreig de bosons és un model restringit de càlcul quàntic no universal introduït per Scott Aaronson i Alex Arkhipov després del treball original de Lidror Troyansky i Naftali Tishby, que va explorar el possible ús de la dispersió dels bosons per avaluar els valors d'expectativa dels permanents de les matrius. El model consisteix en el mostreig de la distribució de probabilitat de bosons idèntics dispersos per un interferòmetre lineal. Tot i que el problema està ben definit per a qualsevol partícula bosònica, la seva versió fotònica es considera actualment la plataforma més prometedora per a una implementació escalable d'un dispositiu de mostreig de bosons, cosa que el converteix en un enfocament no universal de la computació quàntica òptica lineal. A més, encara que no és universal, es creu fermament que l'esquema de mostreig de bosons implementa tasques informàtiques que són difícils d'implementar amb ordinadors clàssics utilitzant molts menys recursos físics que una configuració de computació quàntica òptica lineal completa. Aquest avantatge el converteix en un candidat ideal per demostrar el poder de la computació quàntica a curt termini.

## Descripció

Considereu un circuit òptic lineal multimode de N modes que s'injecta amb M fotons únics indistinguibles (N>M). Aleshores, la implementació fotònica de la tasca de mostreig de bosons consisteix a generar una mostra a partir de la distribució de probabilitat de mesures d'un sol fotó a la sortida del circuit. Concretament, això requereix fonts fiables de fotons únics (actualment els més utilitzats són els cristalls paramètrics de conversió descendent), així com un interferòmetre lineal. Aquests últims es poden fabricar, per exemple, amb divisors de feix de fibra fosa, a través de sílice sobre silici o interferòmetres integrats escrits amb làser o xips òptics amb interfície elèctrica i òptica. Finalment, l'esquema també requereix detectors de recompte de fotons únics d'alta eficiència, com els basats en nanofils superconductors polaritzats pel corrent, que realitzen les mesures a la sortida del circuit. Per tant, basant-se en aquests tres ingredients, la configuració de mostreig de bosons no requereix cap ancilla, mesures adaptatives o operacions d'enredament, com ho fa, per exemple, l'esquema òptic universal de Knill, Laflamme i Milburn (l'esquema KLM). Això el converteix en un model no universal de càlcul quàntic i redueix la quantitat de recursos físics necessaris per a la seva realització pràctica.
Concretament, suposem que l'interferòmetre lineal està descrit per una matriu unitària N×N $U,$ que realitza una transformació lineal dels operadors de creació (aniquilació). $a_{i}^{\dagger }$$(a_{i}^)$ dels modes d'entrada del circuit:
$b_{j}^{\dagger }=\sum _{i=1}^{N}U_{ji}a_{i}^{\dagger }\;\;(b_{j}=\sum _{i=1}^{N}U_{ji}^{*}a_{i}).$
Aquí i ( j ) etiqueta els modes d'entrada (sortida) i $b_{j}^{\dagger }$$(b_{j}^)$ denota els operadors de creació (aniquilació) dels modes de sortida ( i,j =1 ,..., N ). Un interferòmetre caracteritzat per alguns unitaris $U$ indueix naturalment una evolució unitària $\varphi _{M}(U)$ activat $M$ -estats de fotons. A més, el mapa $\varphi _{M}$ és un homomorfisme entre $N$ Matrius unitàries -dimensionals i unitats que actuen sobre l'espai de Hilbert exponencialment gran del sistema: arguments de recompte simples mostren que la mida de l'espai de Hilbert corresponent a un sistema de M fotons indistinguibles distribuïts entre N modes ve donada pel coeficient binomial ${\tbinom {M+N-1}{M}}$ (observeu que com que existeix aquest homomorfisme, no tots els valors de $W$ són possibles).
Suposem que l'interferòmetre s'injecta amb un estat d'entrada de fotons individuals $|\psi _{\text{in}}\rangle =$$|s_{1},s_{2},...,s_{N}\rangle$ amb $\sum _{k=1}^{N}s_{k}=M$$(s_{k}$ és el nombre de fotons injectats en el mode k-è). Després, l'estat $|\psi _{\text{out}}\rangle$ a la sortida del circuit es pot escriure com $|\psi _{\text{out}}\rangle =\varphi _{M}(U)|s_{1},s_{2},...,s_{N}\rangle .$ Una manera senzilla d'entendre l'homomorfisme entre $U$ i $\varphi _{M}(U)$ és el següent:
Definim l'isomorfisme per als estats base: $P_{|s_{1},s_{2},...,s_{N}\rangle }($ x $)\equiv x_{1}^{s_{1}}{\cdot }x_{2}^{s_{2}}{\cdot \cdot \cdot }x_{N}^{s_{N}}$, i obteniu el resultat següent : $P_{{\varphi (U)}|s_{1},s_{2},...,s_{N}\rangle }($ x $)=P_{|s_{1},s_{2},...,s_{N}\rangle }(U$ x $)$
En conseqüència, la probabilitat $p(t_{1},t_{2},...,t_{N})$ de detectar $t_{k}$ fotons al mode de sortida k -è es dóna com a
$p(t_{1},t_{2},...,t_{N})=|\langle t_{1},t_{2},...,t_{N}|\psi _{\text{out}}\rangle |^{2}={\frac {|{\text{Perm}}\,U_{S,T}|^{2}}{t_{1}!\cdot \cdot \cdot t_{N}!s_{1}!\cdot \cdot \cdot s_{N}!}}.$
En l'expressió anterior ${\text{Perm}}\,U_{S,T}$ representa el permanent de la matriu $U_{S,T},$ que s'obté de la unitat $U$ en repetir $s_{i}$ vegades la seva i columna i $t_{j}$ vegades la seva fila j. Normalment, en el context del problema de mostreig de bosons, l'estat d'entrada es pren d'una forma estàndard, denotada com $|1_{M}\rangle ,$ per al qual s'injecta un sol fotó cadascun dels primers modes M de l'interferòmetre. En aquest cas, l'expressió anterior diu:
$p(t_{1},t_{2},...,t_{N})=|\langle t_{1},t_{2},...,t_{N}|\varphi _{M}(U)|1_{M}\rangle |^{2}={\frac {|{\text{Perm}}\,U_{T}|^{2}}{t_{1}!\cdot \cdot \cdot t_{N}!}},$
on la matriu $U_{T}$ s'obté de $U$ mantenint les seves primeres M columnes i repetint $t_{j}$ vegades la seva fila j. Posteriorment, la tasca del mostreig de bosons és fer mostres exactament o aproximadament de la distribució de sortida anterior, donada la unitat unitària. $U$ descrivint el circuit òptic lineal com a entrada. Com es detalla a continuació, l'aparició del permanent a les estadístiques corresponents de mesures d'un sol fotó contribueix a la duresa del problema de mostreig de bosons.

## Complexitat del problema

La raó principal del creixent interès pel model de mostreig de bosons és que, tot i ser no universal, es creu fermament que realitza una tasca computacional que és intractable per a un ordinador clàssic. Una de les raons principals d'això és que la distribució de probabilitat, de la qual ha de mostrejar el dispositiu de mostreig de bosons, està relacionada amb la permanent de matrius complexes. El càlcul del permanent és, en el cas general, una tasca extremadament difícil: es troba en la classe de complexitat #P-hard. A més, la seva aproximació a l'error multiplicatiu també és un problema #P-difícil.
Totes les proves actuals de la duresa de la simulació del mostreig de bosons en un ordinador clàssic es basen en les fortes conseqüències computacionals que tindria la seva simulació eficient mitjançant un algorisme clàssic. És a dir, aquestes proves mostren que una simulació clàssica eficient implicaria el col·lapse de la jerarquia polinomial al seu tercer nivell, una possibilitat que es considera molt poc probable per la comunitat informàtica, a causa de les seves fortes implicacions computacionals (en línia amb les fortes implicacions del problema P=NP).

## Referències

* ↑ Aaronson, Scott; Arkhipov, Alex Theory of Computing, 9, 2013, pàg. 143–252. DOI: 10.4086/toc.2013.v009a004 [Consulta: free].
* ↑ Broome, Matthew; Fedrizzi, Alessandro; Rahimi-Keshari, Saleh; Dove, Justin; Aaronson, Scott Science, 339, 6121, 2013, pàg. 794–798. arXiv: 1212.2234. Bibcode: 2013Sci...339..794B. DOI: 10.1126/science.1231440. PMID: 23258411.
* ↑ Spring, Justin; Metcalf, Benjamin; Humphreys, Peter; Kolthammer, Steven; Jin, Xian-Min Science, 339, 6121, 2013, pàg. 798–801. arXiv: 1212.2622. Bibcode: 2013Sci...339..798S. DOI: 10.1126/science.1231692. PMID: 23258407.
* ↑ Szameit, Alexander; Dreisow, Felix; Pertsch, Thomas; Nolte, Stefan; Tünnermann, Andreas Optics Express, 15, 4, 2007, pàg. 1579–1587. Bibcode: 2007OExpr..15.1579S. DOI: 10.1364/OE.15.001579. PMID: 19532390 [Consulta: free].
* ↑ Tillmann, Max; Dakic, Borivoje; Heilmann, Rene; Nolte, Stefan; Szameit, Alexander Nature Photonics, 7, 7, 2013, pàg. 540–544. arXiv: 1212.2240. Bibcode: 2013NaPho...7..540T. DOI: 10.1038/nphoton.2013.102.
* ↑ Crespi, Andrea; Osellame, Roberto; Ramponi, Roberta; Brod, Daniel; Galvao, Ernesto Nature Photonics, 7, 7, 2013, pàg. 545–549. arXiv: 1212.2783. Bibcode: 2013NaPho...7..545C. DOI: 10.1038/nphoton.2013.112.
* ↑ Carolan, Jacques; Harrold, Christopher; Sparrow, Chris; etal Science, 349, 6249, 2015, pàg. 711–716. arXiv: 1505.01182. DOI: 10.1126/science.aab3642. PMID: 26160375.
* ↑ Scheel, Stefan Acta Physica Slovaca, 58, 5, 2008, pàg. 675. arXiv: quant-ph/0406127. Bibcode: 2004quant.ph..6127S. DOI: 10.2478/v10155-010-0092-x.