¿Es posible "calcular" el valor absoluto de un permanente usando Boson Sampling?

16

En el muestreo de bosones , si comenzamos con 1 fotón en cada uno de los primeros modos M de un interferómetro, la probabilidad de detectar 1 fotón en cada modo de salida es: |Perm(A)|2 , donde las columnas y filas de A son las primeras columnas M de la matriz unitaria del interferómetro U, y todas sus filas.

Esto hace que parezca cualquier unitaria U, podemos construir el interferómetro apropiado, construir la matriz A y calcular el valor absoluto del permanente de A tomando la raíz cuadrada de la probabilidad de detectar un fotón en cada modo (que nosotros obtener del experimento de muestreo de bosones). ¿Es esto cierto o hay alguna trampa? La gente me ha dicho que no se puede obtener información sobre un permanente a partir del muestreo de bosones.

Además, ¿qué sucede con el resto de las columnas de U ? ¿Cómo es exactamente que el resultado experimental solo depende de las primeras columnas M de U y todas sus filas, pero no del todo en las otras columnas de U ? ¿Esas columnas de U no afectan en absoluto el resultado del experimento en los primeros modos M ?

usuario1271772
fuente
Desde que creó la fotónica , considere escribir el extracto de la etiqueta. Ir aquí . Gracias.
Sanchayan Dutta

Respuestas:

7

Parece ser cierto, hasta cierto punto. A medida que leía de Scott Aaronson papel , se dice que si se inicia con 1 fotón en cada uno de los primeros modos de un interferómetro, y encontrar la probabilidad P S que un conjunto s i fotones se emiten en cada modo i { 1 , ... , N } donde i s i = M , es P s = | Por (A) | 2MPSsii{1,,N}isi=M Entonces, de hecho, si toma una instancia particular dondesi=0o 1 para cada salida posible, entonces, sí, la probabilidad es igual al permanente deA, dondeAes la primeraMcolumnas deUy un subconjunto específico deMfilas especificadas por las ubicacionessi=1. Entonces, esto no es exactamente como se especifica en la pregunta: no son todas las filas, sino solo un subconjunto, de modo queA

Ps=|Per(A)|2s1!s2!sM!.
si=0AAMUMsi=1Aes una matriz cuadrada, correspondiente a los bits que el experimento "ve", es decir, las filas de entrada y las filas de salida. Los fotones de cualquier cosa nunca se pueblan el mundo, y también lo son ciegos a los demás elementos de la matriz unitaria .U

Esto debería ser bastante obvio. Digamos que tengo un poco de matriz V . Si empiezo en algún estado base | 0 y encontrar su producto, V | 0 , a continuación, sabiendo que me dice muy poco acerca de las salidas V | 1 y V3×3V|0V|0V|1 , aparte de lo que puede decirse del conocimiento de que V es unitario, y por lo tanto, las columnas y las filas son ortonormales.V|2V

El problema que hay que tener cuidado es la precisión: ejecuta esto una vez y todo lo que obtiene es una sola muestra de acuerdo con la distribución de probabilidad . Ejecutas esto varias veces y comienzas a acumular información sobre las diferentes probabilidades. Ejecutas esto suficientes veces y puedes obtener una respuesta arbitrariamente precisa, pero ¿cuántas es suficiente? Hay dos formas diferentes de medir el error en una estimación de un valor p . Puede exigir un error aditivo p ± ϵ o un error multiplicativo, p ( 1 ±Pspp±ϵ . Como esperamos que una probabilidad típica sea exponencialmente pequeña en n + mp(1±ϵ)n+m, el error multiplicativo exige una precisión mucho mayor, que no se puede lograr de manera eficiente a través del muestreo. Por otro lado, se puede lograr la aproximación de error aditivo.

Mientras que un error multiplicativo es lo que la gente generalmente quiere calcular, el error aditivo también puede ser una entidad interesante. Por ejemplo, en la evaluación del polinomio de Jones .

Aaronson nos señala más atrás en el tiempo sobre dónde se estableció por primera vez esta conexión entre el muestreo Boson y el Permanente:

Se sabe desde el trabajo de Caianiello en 1953 (si no antes) que las amplitudes para los procesos -boson se pueden escribir como los permanentes de las matrices n × n .nn×n

En cambio, su principal contribución

es demostrar una conexión entre la capacidad de las computadoras clásicas para resolver el problema aproximado de BosonSampling y su capacidad para aproximar el problema permanente

es decir, para comprender el problema de aproximación asociado, por ejemplo, al muestreo finito, y para describir las consecuencias de la complejidad computacional asociadas: que creemos que tal cosa es difícil de evaluar clásicamente.

DaftWullie
fuente
No estoy seguro de si esto es lo que está diciendo, pero no es cierto que resolver de manera eficiente BosonSampling permita estimar de manera eficiente los permanentes, lo que implicaría que las computadoras cuánticas pueden resolver problemas difíciles de # P. En otras palabras, las computadoras cuánticas pueden simular eficientemente la salida de una muestra de bosones, pero no pueden calcular eficientemente su distribución de probabilidad de salida
glS
@glS No, eso es mucho lo que digo. El documento de Aaronson es muy cuidadoso para distinguir ese problema, pero hace que la declaración de complejidad computacional sea mucho más desordenada, por lo que no lo dije.
DaftWullie
@DaftWullie lo siento, ahora estoy confundido. ¿Estamos de acuerdo en que el muestreo de bosones no permite estimar permanentemente los permanentes? (véase, por ejemplo, la parte inferior de la columna izquierda en la página 6 de arxiv.org/pdf/1406.6767.pdf )
glS
@gls Estoy de acuerdo en que no puede hacerlo si desea una estimación del permanente con algún error multiplicativo vinculado, que, sin duda, es la forma estándar de definir las cosas (pero como evité cuidadosamente definir cualquier cosa ...). Si está dispuesto a tolerar un error aditivo vinculado, entonces creo que puede hacerlo.
DaftWullie
"Si comienzo en algún estado base y encontrar su producto, V | 0 , a continuación, sabiendo que me dice muy poco acerca de las salidas V | 1 y V | 2 ", pero cada elemento de V está involucrado en darle V | 0 . Pero para el muestreo de bosones, solo están involucradas las primeras columnas M , ¿no es sorprendente? |0V|0V|1V|2VV|0M
user1271772
6

No puedes recuperar eficientemente los valores absolutos de las amplitudes, pero si permite muchas muestras arbitrarias, puede estimarlas con el grado de precisión que desee.

Más específicamente, si el estado de entrada es un fotón único en cada uno de los primeros modos, y uno está dispuesto a extraer un número arbitrario de muestras de la salida, entonces, en principio, es posible estimar el permanente de A a cualquier grado de precisión que le gusta, contando la fracción de veces que los n fotones de entrada salen en los primeros n puertos de salida diferentes. Sin embargo, debe tenerse en cuenta que esto realmente no tiene mucho que ver con BosonSampling, ya que el resultado de la dureza se mantiene en el régimen del número de modos mucho más grande que el número de fotones, y se trata de la eficiencia del muestreo.nAnn

BosonSampling

Intentaré una breve introducción a lo que es el muestreo de bosones, pero cabe señalar que no puedo hacer un mejor trabajo en esto que el propio Aaronson, por lo que probablemente sea una buena idea echar un vistazo a las publicaciones relacionadas de su blog. (por ejemplo, blog /? p = 473 y blog /? p = 1177 ), y enlaces en los mismos.

BosonSampling es un problema de muestreo . Esto puede ser un poco confuso ya que las personas generalmente están más acostumbradas a pensar en problemas que tienen respuestas definitivas. Un problema de muestreo es diferente porque la solución al problema es un conjunto de muestras extraídas de alguna distribución de probabilidad.

De hecho, el problema que resuelve una muestra de bosones es el muestreo de una distribución de probabilidad específica. Más específicamente,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 possible output two-photon states: (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)

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/

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