Можно ли «рассчитать» абсолютное значение перманента с помощью бозонной выборки?

16

В бозонной выборке , если мы начнем с 1 фотона в каждой из первых M мод интерферометра, вероятность обнаружения 1 фотона в каждой выходной моде равна: |Perm(A)|2 , где столбцы и строки A являются первыми M столбцами унитарной матрицы интерферометра и всех ее строк.U

Это выглядит как для любого унитарного , мы можем построить соответствующий интерферометр, построить матрицу и вычислить абсолютное значение перманента , взяв квадратный корень из вероятности обнаружения одного фотона в каждой моде (который мы получить из эксперимента по отбору проб бозонов). Это правда, или есть какой-то подвох? Люди говорили мне, что вы не можете получить информацию о перманенте из бозонной выборки.UAA

Кроме того, что происходит с остальными столбцами : Как именно экспериментальный результат зависит только от первых столбцов и всех его строк, но никак не от других столбцов ? Эти столбцы вообще не влияют на исход эксперимента в первых режимах?M U U U MUMUUUM

user1271772
источник
Поскольку вы создали фотонику , подумайте над тем, чтобы написать для нее отрывок тега. Иди сюда . Спасибо.
Санчайан Датта

Ответы:

7

Кажется, это правда, до определенного момента. Как я прочитал Ааронсон в бумагу , он говорит , что если вы начинаете с 1 фотоном в каждом из первых M режимов интерферометра, и найти вероятность PS , что множество si фотоны выводятся в каждом режиме i{1,,N} где isi=M , есть

Ps=|Per(A)|2s1!s2!sM!.
Таким образом, действительно, если вы берете конкретный экземпляр, гдеsi=0или 1 для каждого возможного выхода, то да, вероятность равна перманентуA, гдеA- это первыеMстолбцовUи конкретное подмножествоMстроки, определенные местоположениямиsi=1. Таким образом, это не совсем так, как указано в вопросе: это не все строки, а только некоторое подмножество, так чтоAквадратная матрица, соответствующая битам, которые «видит» эксперимент, т.е. входные строки и выходные строки. Фотоны никогда Заселите что - нибудь еще, и поэтому закрывают глаза на другие элементы унитарной матрицы .U

Это должно быть довольно очевидно. Скажем , у меня есть матрицы V . Если я начну в каком-то базовом состоянии | 0 и найти свой продукт, V | 0 , то , зная , что говорит мне , очень мало о выходах V | 1 и V | 2 , в стороне от того, что можно сказать , из знания , что V является унитарным, и , следовательно , столбцы и строки ортонормированы.3×3V|0V|0V|1V|2V

Проблема, с которой нужно быть осторожным, заключается в точности: вы запускаете это один раз, и все, что вы получаете, это одна выборка в соответствии с распределением вероятности . Вы запускаете это несколько раз, и вы начинаете собирать информацию о различных вероятностях. Вы запускаете это достаточно много раз, и вы можете получить произвольно точный ответ, но сколько достаточно? Существует два разных способа измерения ошибки при оценке значения p . Вы можете потребовать либо аддитивную ошибку p ± ϵ, либо мультипликативную ошибку p ( 1 ± ϵ ) . Поскольку мы ожидаем, что типичная вероятность будет экспоненциально мала по n + mPspp±ϵp(1±ϵ)n+mмультипликативная ошибка требует гораздо большей точности, которая не может быть эффективно достигнута с помощью выборки. С другой стороны, приближение аддитивной ошибки может быть достигнуто.

В то время как мультипликативная ошибка - это то, что люди обычно хотят вычислить, аддитивная ошибка также может быть интересной сущностью. Например, в оценке многочлена Джонса .

Ааронсон еще раз указывает нам на то, где впервые была установлена ​​связь между отбором проб Бозона и Перманентом:

Со времени работы Кайанелло в 1953 году (если не раньше) было известно, что амплитуды для процессов бозона могут быть записаны как перманенты матриц n × n .nn×n

Вместо этого их основной вклад

является доказательством связи между способностью классических компьютеров решать приближенную проблему BosonSampling и их способностью приближать постоянную

то есть понять проблему аппроксимации, связанную, например, с конечной выборкой, и описать связанные с этим последствия вычислительной сложности: мы считаем, что такую ​​вещь трудно оценить классически.

DaftWullie
источник
Я не уверен, что это то, что вы говорите, но это неправда, что эффективное решение BosonSampling позволяет эффективно оценивать перманенты, что подразумевает, что квантовые компьютеры способны решать # P-сложные задачи. Другими словами, квантовые компьютеры могут эффективно моделировать выходной сигнал бозонного пробоотборника, но не могут эффективно вычислять его распределение выходной вероятности
glS
@glS Нет, это очень много, что я говорю. В статье Ааронсона очень тщательно выявляется эта проблема, но она усложняет задачу определения сложности вычислений, поэтому я не стал ее указывать.
DaftWullie
@DaftWullie извините, теперь я в замешательстве. Согласны ли мы с тем, что выборка бозонов не позволяет эффективно оценить перманенты? (см., например, нижнюю часть левой колонки на странице 6 arxiv.org/pdf/1406.6767.pdf )
GLS
@gls Я согласен, что вы не можете сделать это, если хотите получить оценку перманента с некоторой мультипликативной оценкой ошибки, которая, по общему признанию, является стандартным способом определения вещей (но так как я тщательно избегал определения чего-либо ...). Если вы готовы смириться с аддитивной ошибкой, то, я думаю, вы можете это сделать.
DaftWullie
«Если я начну в некотором базисном состоянии и найти его продукт, V | 0 , то , зная , что говорит мне , очень мало о выходах V | 1 и V | 2 », но каждый элемент V участвует в предоставлении вам V | 0 . Но для бозонной выборки задействованы только первые М столбцов, не правда ли? |0V|0V|1V|2VV|0M
user1271772
6

Вы не можете эффективно восстановить абсолютные значения амплитуд, но если вы разрешите произвольное количество выборок, вы сможете оценить их с любой степенью точности, которая вам нравится.

Более конкретно, если входное состояние представляет собой одиночный фотон в каждой из первых мод, и каждый желает извлечь произвольное количество выборок из выходного сигнала, то в принципе возможно оценить перманент A до любой степени Точность, которая нравится, подсчитывая, сколько раз n входных фотонов выходят из первых n различных выходных портов. Следует отметить, однако, что это не имеет большого отношения к BosonSampling, поскольку результат твердости сохраняется в режиме с числом мод, значительно превышающим число фотонов, и это касается эффективности дискретизации.nAnn

BosonSampling

Я попробую очень краткое введение в то, что такое бозонная выборка, но следует отметить, что я не могу лучше справиться с этим, чем сам Ааронсон, так что, вероятно, будет хорошей идеей взглянуть на соответствующие сообщения в блоге его (например, blog /? p = 473 и blog /? p = 1177 ) и ссылки в них.

BosonSampling - это проблема выборки . Это может немного смущать, так как люди обычно привыкли думать о проблемах с определенными ответами. Проблема выборки отличается тем, что решением проблемы является набор выборок, взятых из некоторого распределения вероятности.

Действительно, проблема, которую решает бозонный пробоотборник, заключается в том, чтобы отбирать образцы из определенного распределения вероятностей. Более конкретно, выборка из распределения вероятностей возможных конечных (многозонных) состояний.

Рассмотрим в качестве простого примера случай с 2-мя фотонами в 4-х режимах, и предположим, что мы зафиксировали входное состояние как (то есть, один фотон в каждом из двух первых двух режимов ввода). Игнорируя выходные состояния с более чем одним фотоном в каждой моде, есть ( 4(1,1,0,0)|1,1,0,0возможных выходных двухфотонных состояний: (1,1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,0),(0,1,0,1)и(0,(42)=6(1,1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,0),(0,1,0,1) . Обозначим для удобства с о я , я = 1 , . , 6 я -м один (так, например, о 2 = ( 1 , 0 , 1 , 0 ) ). Тогда возможным решением BosonSampling может быть ряд результатов: o 1 , o 4 , o 2 , o 2 , o 5 .(0,0,1,1)oi,i=1,.,6io2=(1,0,1,0)

o1,o4,o2,o2,o5.

Чтобы провести аналогию с, возможно, более знакомым случаем, это все равно, что сказать, что мы хотим взять выборку из гауссовского распределения вероятностей. Это означает, что мы хотим найти последовательность чисел, которая, если мы нарисуем их достаточно и поместим их в гистограмму, будет производить нечто, близкое к гауссовскому.

Вычислительные перманенты

Оказывается, что амплитуда вероятности заданного входного состояния на заданном выходном состоянии | с есть (пропорционально к нему ) постоянной подходящей матрице , построенной из унитарной матрицы , характеризующей (однобозонная) эволюцию.|r|s

Более конкретно, если обозначает список назначений режимаR(1)|rS|sUA(rs)|r|s

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
источник
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