Czy można „obliczyć” wartość bezwzględną wartości stałej przy użyciu próbkowania bozonu?


16

W próbkowaniu bozonu , jeśli zaczynamy od 1 fotonu w każdym z pierwszych trybów M interferometru, prawdopodobieństwo wykrycia 1 fotonu w każdym trybie wyjściowym wynosi: |Perm(A)|2 , gdzie kolumny i rzędy A są pierwszymi M kolumnami jednolitej macierzy U interferometruU i wszystkimi jego rzędami.

To sprawia, że ​​wygląda jak dowolny jednostkowy U , możemy skonstruować odpowiedni interferometr, skonstruować macierz A i obliczyć wartość bezwzględną stałej A , przyjmując pierwiastek kwadratowy z prawdopodobieństwa wykrycia jednego fotonu w każdym trybie ( pobrać z eksperymentu z bozonem). Czy to prawda, czy jest jakiś haczyk?Ludzie mówili mi, że tak naprawdę nie można uzyskać informacji na temat stałej z próbkowania bozonu.

Co się dzieje z resztą kolumn : Jak dokładnie jest tak, że wynik eksperymentu zależy tylko od pierwszych M kolumn U i wszystkich jego wierszy, ale wcale nie od pozostałych kolumn U ? Te kolumny U w ogóle nie wpływają na wynik eksperymentu w pierwszych trybach M ?UMUUUM


Ponieważ stworzyłeś fotonikę , zastanów się nad napisaniem tego fragmentu tagu. Przejdź tutaj . Dziękuję Ci.
Sanchayan Dutta

Odpowiedzi:


7

Do pewnego stopnia wydaje się to prawdą. Jak czytam Scott Aaronson za papier , to mówi, że jeśli zaczniesz z 1 fotonu w każdym z pierwszych trybów interferometr i znaleźć prawdopodobieństwo P S że zestaw s I fotonów jest odtwarzany w każdym trybie í { 1 , ... , N } gdzie i s i = M , oznacza P s = | Na (A) | 2)MPSsii{1,,N}isi=M Tak więc, jeśli weźmiesz konkretny przypadek, w którymsi=0lub 1 dla każdego możliwego wyniku, to tak, prawdopodobieństwo jest równe stałejA, gdzieAjest pierwsząMkolumnamiUi określonym podzbioremMwiersze określone przez lokalizacjesi=1. Tak więc nie jest to dokładnie tak, jak określono w pytaniu: to nie wszystkie wiersze, ale tylko niektóre podzbiory, więcA

Ps=|Per(A)|2s1!s2!sM!.
si=0AAMUMsi=1Ajest kwadratową macierzą, odpowiadającą bitom, które „widzi” eksperyment, tj. rzędy wejściowe i wyjściowe. Fotony nigdy Populate cokolwiek innego, i tak są ślepi na inne elementy macierzy jednostkowej .U

To powinno być dość oczywiste. Powiedzmy, że mam macierz V . Jeśli zacznę w jakimś stanie bazowym | 0 i znaleźć swój produkt, V | 0 , to wiedząc, że mówi mi bardzo niewiele o wyjściach V | 1 i V | 2 , oprócz tego, co można powiedzieć, ze świadomością, że V3×3V|0V|0V|1V|2V jest jednolita, a zatem kolumn i wierszy są ortonormalna.

Problem, że trzeba uważać na to dokładność: uruchomić ten jeden raz i wszystko masz to pojedyncza próbka według rozkładu prawdopodobieństwa . Uruchamiasz to kilka razy i zaczynasz gromadzić informacje o różnych prawdopodobieństwach. Wykonujesz to wystarczająco dużo razy i możesz uzyskać dowolną dokładną odpowiedź, ale ile to wystarczy? Istnieją dwa różne sposoby pomiaru błędu w oszacowaniu wartości p . Możesz zażądać albo błędu addytywnego p ± ϵ lub błędu multiplikatywnego, p ( 1 ± ϵ ) . Ponieważ oczekujemy, że typowe prawdopodobieństwo będzie wykładniczo małe w n + mPspp±ϵp(1±ϵ)n+m, błąd multiplikatywny wymaga znacznie większej dokładności, której nie można skutecznie osiągnąć poprzez próbkowanie. Z drugiej strony można osiągnąć aproksymację błędu addytywnego.

Chociaż błąd multiplikatywny jest tym, co ludzie zwykle chcą obliczyć, błąd addytywny może być również interesującą jednostką. Na przykład w ocenie wielomianu Jonesa .

Aaronson wskazuje nam cofnięcie się w czasie, kiedy to połączenie pomiędzy pobieraniem próbek Boson i Permanent zostało po raz pierwszy utworzone:

Od czasu pracy Caianiello w 1953 r. (Jeśli nie wcześniej) wiadomo, że amplitudy procesów Boson można zapisać jako stałe macierzy n × n .nn×n

Zamiast tego ich główny wkład

ma udowodnić związek między zdolnością klasycznych komputerów do rozwiązania przybliżonego problemu BosonSampling a ich zdolnością do przybliżenia stałego

tzn. zrozumieć problem aproksymacji związany np. z próbkowaniem skończonym i opisać związane z tym konsekwencje złożoności obliczeniowej: że naszym zdaniem trudno jest klasycznie ocenić taką rzecz.


Nie jestem pewien, czy to jest to, co mówisz, ale nie jest prawdą, że skuteczne rozwiązanie BosonSampling pozwala na efektywne oszacowanie wartości stałych, co oznaczałoby, że komputery kwantowe są w stanie rozwiązać problemy # P-trudne. Innymi słowy, komputery kwantowe mogą skutecznie symulować moc wyjściową próbnika bozonu, ale nie mogą skutecznie obliczać rozkładu prawdopodobieństwa mocy wyjściowej
glS

@glS Nie, to bardzo mówię. Artykuł Aaronsona bardzo ostrożnie rozróżnia ten problem, ale czyni obliczenie złożoności obliczeniowej o wiele bardziej chaotycznym, dlatego tego nie powiedziałem.
DaftWullie

@DaftWullie przepraszam, teraz jestem zdezorientowany. Czy zgadzamy się, że pobieranie próbek bozonów nie pozwala na skuteczne oszacowanie wartości stałych? (patrz na przykład dno z lewej kolumny w pag 6 arxiv.org/pdf/1406.6767.pdf )
G

@gls Zgadzam się, że nie możesz tego zrobić, jeśli chcesz oszacować stałą z pewnym błędem multiplikatywnym, co, co prawda, jest standardowym sposobem definiowania rzeczy (ale ponieważ ostrożnie unikałem definiowania czegokolwiek ...). Jeśli chcesz tolerować błąd związany z addytywnym błędem, to wierzę, że możesz to zrobić.
DaftWullie

„Jeśli zacznę w jakimś stanie Podstawa i znaleźć swój produkt, V | 0 , to wiedząc, że mówi mi bardzo niewiele o wyjściach V | 1 i V | 2 ”, ale każdy pojedynczy element V jest zaangażowany dając ci V | 0 . Ale w przypadku próbkowania bozonów zaangażowane są tylko pierwsze kolumny M , czy to nie jest niesamowite? |0V|0V|1V|2VV|0M
user1271772,

6

Nie można skutecznie odzyskać bezwzględnych wartości amplitud, ale jeśli zezwolisz na dowolne wiele próbek, możesz je oszacować z dowolnym stopniem dokładności, jaki ci się podoba.

Mówiąc dokładniej, jeśli stanem wejściowym jest pojedynczy foton w każdym z pierwszych trybów, a ktoś chce wyciągnąć dowolną liczbę próbek z wyjścia, wówczas w zasadzie możliwe jest oszacowanie stałej A do dowolnego stopnia dokładność, którą się lubi, licząc ułamek czasu, w którym n fotonów wejściowych wychodzi w pierwszych n różnych portach wyjściowych. Należy jednak zauważyć, że tak naprawdę nie ma to wiele wspólnego z BosonSampling, ponieważ wynik twardości dotyczy reżimu liczby modów znacznie większych niż liczba fotonów, a chodzi o wydajność próbkowania.nAnn

BosonSampling

Spróbuję bardzo krótkiego wprowadzenia do tego, czym jest próbkowanie bozonów, ale należy zauważyć, że nie mogę wykonać lepszej pracy niż sam Aaronson, więc prawdopodobnie dobrym pomysłem jest przejrzenie powiązanych postów na jego blogu (np. blog /? p = 473 i blog /? p = 1177 ) i odnośniki do nich.

BosonSampling to problem z próbkowaniem . Może to być nieco mylące, ponieważ ludzie są zwykle bardziej przyzwyczajeni do myślenia o problemach z konkretnymi odpowiedziami. Problem próbkowania różni się tym, że rozwiązaniem problemu jest zestaw próbek pobranych z pewnego rozkładu prawdopodobieństwa.

Indeed, the problem a boson sampler solves is that of sampling from a specific probability distribution. More specifically, sampling from the probability distribution of the possible outcome (many-boson) states.

Consider as a simple example a case with 2 photons in 4 modes, and let's say we fix the input state to be (1,1,0,0)|1,1,0,0 (that is, a single photon in each of the two first two input modes). Ignoring the output states with more than one photon in each mode, there are (42)=6(1,1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,0),(0,1,0,1) and (0,0,1,1)oi,i=1,.,6io2=(1,0,1,0)). Then, a possible solution to BosonSampling could be the series of outcomes:

o1,o4,o2,o2,o5.

To make an analogy to a maybe more familiar case, it's like saying that we want to sample from a Gaussian probability distribution. This means that we want to find a sequence of numbers which, if we draw enough of them and put them into a histogram, will produce something close to a Gaussian.

Computing permanents

It turns out that the probability amplitude of a given input state |r to a given output state |s is (proportional to) the permanent of a suitable matrix built out of the unitary matrix characterizing the (single-boson) evolution.

More specifically, if R denotes the mode assignment list(1) associated to |r, S that of |s, and U is the unitary matrix describing the evolution, then the probability amplitude A(rs) of going from |r to |s is given by

A(rs)=1r!s!permU[R|S],
with U[R|S] denoting the matrix built by taking from U the rows specified by R and the columns specified by S.

Thus, considering the fixed input state |r0, the probability distribution of the possible outcomes is given by the probabilities

ps=1r0!s!|permU[R|S]|2.

BosonSampling is the problem of drawing "points" according to this distribution.

This is not the same as computing the probabilities ps, or even computing the permanents themselves. Indeed, computing the permanents of complex matrices is hard, and it is not expected even for quantum computers to be able to do it efficiently.

The gist of the matter is that sampling from a probability distribution is in general easier than computing the distribution itself. While a naive way to sample from a distribution is to compute the probabilities (if not already known) and use those to draw the points, there might be smarter ways to do it. A boson sampler is something that is able to draw points according to a specific probability distribution, even though the probabilities making up the distribution itself are not known (or better said, not efficiently computable).

Furthermore, while it may look like the ability to efficiently sample from a distribution should translate into the ability of efficiently estimating the underlying probabilities, this is not the case as soon as there are exponentially many possible outcomes. This is indeed the case of boson sampling with uniformly random unitaries (that is, the original setting of BosonSampling), in which there are (mn) possible n-boson in m-modes output states (again, neglecting states with more than one boson in some mode). For mn, this number increases exponentially with n. This means that, in practice, you would need to draw an exponential number of samples to even have a decent chance of seeing a single outcome more than once, let alone estimate with any decent accuracy the probabilities themselves (it is important to note that this is not the core reason for the hardness though, as the exponential number of possible outcomes could be overcome with smarter methods).

In some particular cases, it is possible to efficiently estimate the permanent of matrices using a boson sampling set-up. This will only be feasible if one of the submatrices has a large (i.e. not exponentially small) permanent associated with it, so that the input-output pair associated with it will happen frequently enough for an estimate to be feasible in polynomial time. This is a very atypical situation, and will not arise if you draw unitaries at random. For a trivial example, consider matrices that are very close to identity - the event in which all photons come out in the same modes they came in will correspond to a permanent which can be estimated experimentally. Besides only being feasible for some particular matrices, a careful analysis of the statistical error incurred in evaluating permanents in this way shows that this is not more efficient than known classical algorithms for approximating permanents (technically, within a small additive error) (2).

Columns involved

Let U be the unitary describing the one-boson evolution. Then, basically by definition, the output amplitudes describing the evolution of a single photon entering in the k-th mode are in the k-th column of U.

The unitary describing the evolution of the many-boson states, however, is not actually U, but a bigger unitary, often denoted by φn(U), whose elements are computed from permanents of matrices built out of U.

Informally speaking though, if the input state has photons in, say, the first n modes, then naturally only the first n columns of U must be necessary (and sufficient) to describe the evolution, as the other columns will describe the evolution of photons entering in modes that we are not actually using.


(1) This is just another way to describe a many-boson state. Instead of characterizing the state as the list of occupation numbers for each mode (that is, number of bosons in first mode, number in second, etc.), we characterize the states by naming the mode occupied by each boson. So, for example, the state (1,0,1,0) can be equivalently written as (1,3), and these are two equivalent ways to say that there is one boson in the first and one boson in the third mode.

(2): S. Aaronson and T. Hance. "Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent". https://eccc.weizmann.ac.il/report/2012/170/


I started with 1 photon in each input mode, and said we're looking at the probability of having 1 photon in each output mode, so that we could avoid all these more complicated general equations involving the permanent, which you provide. In fact if M is the number of columns in U, we get that the probability of having 1 photon in each output mode is |Perm(U)|2 from which we can easily get |Perm(U)|. If we let the experiment go on for long enough and get enough samples, can we not obtain an estimate for |Perm(U)| ?
user1271772

In no part of the question did I mention "efficiency" or "sub-exponentially". I'm just interested to know whether or not it's possible to estimate |Perm(U)| using boson sampling.
user1271772

@user1271772 I see. That's the standard way of talking about these things in this context so I might have automatically assumed you meant to talk about efficiency. If you don't care about the number of samples you have to draw then sure, you can compute the output probability distribution, and therefore the absolute values of the permanents, to whatever accuracy you like
glS

@gIS, Aram Harrow once told me you cannot calculate Permanents using boson sampling, so I thought there was some "catch". The best classical algorithm for simulation of exact boson sampling is: O(m2n+mn2), for n photons in m output modes, what is the cost using the interferometer?
user1271772

@user1271772 I answered more specifically your first point in the edit. I guess I got confused because the setting you are mentioning does not seem to have really much to do with boson sampling, but is more generally about the dynamics of indistinguishable bosons through an interferometer
glS
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.