Какой уровень «достоверности» результата от квантового компьютера возможен?

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

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

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

Большинство полезных / относительно эффективных алгоритмов ¹ для квантовых компьютеров относятся к классу сложности « квантовый полиномиальное время с ограниченной ошибкой» (BQP) . Согласно этому определению, вы хотите, чтобы «частота отказов» любого квантового алгоритма была , или , хотя результат все еще может быть в пределах небольшой ошибки. Невероятностный алгоритм (который может выполняться за полиномиальное время) все еще будет в этом классе сложности, с той лишь разницей, что он всегда возвращает правильный результат ² .$\leq\frac{1}{3}$$\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$

Однако, поскольку вы можете запускать алгоритм произвольное количество раз, это эквивалентно вероятности успеха не менее для ввода длины и любой положительной константы .$\frac{1}{2} + n^{-c}$$n$$c$

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

Помимо этих (или других алгоритмов, которые не имеют ни одного «правильного результата»), если вы найдете алгоритм с частотой успеха ниже половины, он больше не является «ограниченной ошибкой» и может оказаться невозможным для пользователя. знать правильный результат - может быть просто неправильный ответ с большей вероятностью, чем правильный.

Да, вы можете видеть разные результаты каждый раз, когда запускаете расчет. Уверенность в результате обеспечивается:

1. Сам квантовый алгоритм, гарантирующий, что правильный результат происходит с высокой вероятностью и;
2. Повторить алгоритм несколько раз, чтобы найти наиболее вероятный результат.

^{1 Здесь алгоритмы, которые можно вычислить за полиномиальное время, чтобы дать решение с «высокой вероятностью», хотя для целей этого ответа временная сложность имеет меньшее значение}

^{+2 ну идеалистично хотя бы}

Разрабатывая Mithrandir24601ответ на вопрос -

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

Например, ваш квантовый компьютер может дать вам правильный ответ на вопрос ДА / НЕТ два раза из каждых трех. Это может показаться низкой производительностью, но это означает, что если вы запускаете его много раз, вы можете просто принять ответ большинства и быть очень уверенным, что правило большинства дает вам правильный ответ. (То же самое относится и к обычным рандомизированным вычислениям.) То, как достоверность увеличивается с увеличением числа рун, означает, что, если любой прогон дает ответ, который имеет значительно более чем 50% -ную вероятность быть правильной, Вы можете повысить свою уверенность настолько, насколько пожелаете, просто сделав скромное количество повторных прогонов (хотя требуется больше прогонов, чем меньше вероятность правильного ответа в любом прогоне до 50%).

$\mathrm{poly}(n)$$n$

Для задач, которые имеют более сложные ответы, чем вопросы ДА / НЕТ, мы не можем обязательно предполагать, что один и тот же ответ будет получен более одного раза, чтобы мы могли получить большинство голосов. (Если вы используете квантовый компьютер для выборки из экспоненциального числа результатов, возможно, что есть меньшее, но все же экспоненциально большое количество ответов, которые являются правильными и полезными!) Предположим, что вы пытаетесь решить проблему оптимизации: может быть нелегко проверить, что вы нашли оптимальное решение или почти оптимальное решение - или что полученный вами ответ - даже лучшее, что может сделать квантовый компьютер (что, если следующий запуск даст вам лучше ответь случайно?). В этом случае важно определить, что вы знаете о проблеме,NP , а это означает, что вы в принципе можете эффективно проверить любой ответ, который вам дали?), И каким качеством решения вы были бы довольны.

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

$15$$3\times5$

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

$15$$3$$15$$5$$15=3\times 5$

$\mathsf{FACTORING}$$\mathrm{BQP}\cap\mathrm{NP}$$\mathrm{BQP}$

$\mathrm{BQP}$$\mathrm{NP}$

(Я знаю, что уже есть два отличных ответа; однако этот вопрос позволяет изложить / уточнить цитату / анектдот Ааронсона.)