Действительно ли реализация алгоритма Шора в 2016 году действительно масштабируема?

В научной статье 2016 года « Реализация масштабируемого алгоритма Шора » [ 1 ] авторы учитывают 15 с только 5 кубитами, что меньше «требуемых» 8 кубитов согласно Таблице 1 в [ 2 ] и Таблице 5 из [ 3 ]. Требование 8- кубитов исходит из конца [ 4 ], в котором говорится, что количество кубитов, необходимых для разложения числа, равно что для 15 равно . $n$ $1.5n+2$ $1.5\cdot 4 + 2=8$

В статье, в которой используются только 5 кубитов, говорится, что их алгоритм «заменяет КТП, действующее на М кубитов, на квазиклассическое КТП, действующее многократно на одном кубите», но последствия этого для сложности алгоритма никогда не упоминались в статье.

Теперь была резкая критика статьи, в которой утверждается, что фактор 15 «масштабируем», как говорится в разделе 2, что аргумент сложности для алгоритма Шора больше не выполняется. Однако эта критика нигде не была подтверждена, и научная статья продолжает отмечаться как «масштабируемая» версия алгоритма Шора. В чем сложность «масштабируемого» алгоритма Шора?

[ 1 ] Монц и соавт. (2016) Наука . Том 351, Issue 6277, pp. 1068-1070
[ 2 ] Смолин и соавт. (2013) Природа . 499, 163–165
[ 3 ] Dattani & Bryans (2014) arXiv: 1411.6758
[ 4 ] Zalka (2008) arXiv: Quant-Ph / 0601097
[ 5 ] Цао и Ло "Комментарий: реализация масштабируемого алгоритма Шора"

cc.complexity-theory ds.algorithms quantum-computing factoring security user1271772
источник

Зависит от того, что вы подразумеваете под «масштабируемым». Некоторые критические замечания в отношении Цао и Лю кажутся довольно придирчивыми. Например, одна из их критики заключается в том, что Китаев не утверждал, что вы можете использовать только один кубит в статье, приведенной для этого результата. Кажется, они не выясняют, является ли это утверждение на самом деле истинным или ложным. Алгоритм Китаева может быть фактически изменен, чтобы использовать только один кубит, как утверждает научная статья, хотя этого утверждения, похоже, нет в статье Китаева о его алгоритме.

Питер Шор

@PeterShor, какая честь слышать от вас! Итак, авторы (правильно) расширили результаты работы Китаева, чтобы сделать это возможным с одним кубитом, и Цао и Лю жалуются, что они называют его «алгоритмом Китаева», а не «модифицированным алгоритмом Китаева или чем-то в этом роде». Тем не менее, они также говорят, что аргумент сложности больше не действует, когда QFT превращается в «полуклассическую QFT». Я все еще студент, когда дело доходит до такого анализа, поэтому я был бы признателен за вклад. Сложность все еще O (log n) ^ 3? Это все еще "масштабируемый" с точки зрения того, чтобы быть полиномиальным, или по крайней мере <GNFS?

user1271772

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

Питер Шор

Эти формулы, которые достигают 8 кубитов, берут некоторую конкретную реализацию алгоритма Шора и вычисляют, сколько кубитов занимает эта реализация. Они не утверждают, что это наилучшая возможная реализация.

Питер Шор

@ user1271772 Это было отмечено модератором, поскольку вы являетесь одним из авторов, упомянутых в вашем посте. Не то чтобы это плохо, некоторая самореклама - неизбежная часть науки, но, может быть, лучше всего прояснить это?

Бьёрн Кьос-Ханссен

Основная идея аргумента Цао и Луо состоит в том, что в варианте алгоритма, который был реализован, первый регистр, который в конечном итоге содержит выходные данные, содержит только 1 бит. И если вы получаете только 1 бит вывода из алгоритма, этого недостаточно для факторизации. (Во-первых, хотя это не их аргумент, 1 бит явно не содержит достаточно информации для определения факторов.)

$c$ $O(\log^3 N)$

Чтобы попытаться быть справедливыми по отношению к Цао и Луо, они говорят, что не думают, что этот алгоритм работает, и если он работает, то это не алгоритм Шора, потому что он не совсем соответствует алгоритму, описанному в оригинальной статье факторинга. , Цитата из их статьи:

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

И действительно, это не алгоритм из моей оригинальной статьи о факторинге. Он использует процедуру оценки фазы из алгоритма факторинга Китаева, а также вариант, открытый Гриффитсом и Ниу (а не Паркером и Пленио, как я уже говорил в предыдущем редактировании этого ответа), который позволяет алгоритму вывести оценку фазы один бит за раз.

Питер Шор
источник

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

Питер Шор

c

$c$

x \cdot t

$x\cdot t$

t

$t$

Я не собираюсь проходить схему для оценки выходной фазы в один кубит и объяснять, почему относительно небольшое изменение, необходимое для достижения этой цели, не влияет на сложность времени. Это «пол-классическая» модификация описанная на странице 2 Parker и Plenio лет бумаги , эффективного разложение с помощью одного чистого кубите и войти N смешанные кубиты .

Питер Шор

\log N + 1

$\log N + 1$

1

$1$

\log N + 1

$\log N + 1$

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

Питер Шор

Действительно ли реализация алгоритма Шора в 2016 году действительно масштабируема?

Ответы: