Существует ли квантовый алгоритм NC для вычисления GCD?

14

Из комментариев на один из моих вопросов о MathOverflow у меня возникает ощущение, что вопрос о GCD в vs. похож на вопрос о целочисленной факторизации в vs. .NСппNп

Существует ли что-то вроде алгоритма «квант » для GCD, поскольку существует алгоритм квантового полиномиального времени ( ) для целочисленной факторизации?NСВQп

Связанный вопрос: сложность наибольшего общего делителя (gcd)

cc.complexity-theory quantum-computing dc.parallel-comp nt.number-theory comp-number-theory Т ....
источник
5
когда вы кросс-пост, лучше написать вопрос снова.
Алессандро Косентино

Ответы:

14

Прежде всего, существует формальное определение «квант-NC», см. QNC в зоопарке.

GCD действительно хороший кандидат на решение проблемы, которая может быть показана в QNC, но она неизвестна в NC. Однако поиск алгоритма QNC для GCD остается открытой проблемой.

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

Ссылка: Заключительный раздел «Р. Клеве и Дж. Уотруса, Быстрые параллельные схемы для квантового преобразования Фурье», arXiv: quant-ph / 0006004

Алессандро Косентино
источник
6
Было бы хорошо, если бы вы могли объяснить связь между квантовым преобразованием Фурье и GCD.
Каве
Я согласен с Каве. Было бы неплохо обеспечить связь.
T ....
2
Я не думаю, что есть прямая связь. Я хотел сказать, что мы подозреваем, что QNC будет более мощным, чем NC, потому что мы можем делать QFT в QNC. Поэтому мы спрашиваем, есть ли еще какая-то более естественная проблема, которая есть и в QNC, и одной из самых простых естественных проблем, которую мы не знаем, как это сделать в NC, является GCD. В какой-то момент я подозревал, что между этими двумя проблемами существует связь, обусловленная тем фактом, что QFT и GCD оба используются в качестве подпрограмм в алгоритме нахождения периода, но я не смог сделать это формальным. Может быть, другие пользователи могут просветить нас больше.
Алессандро Косентино
Привет Алессандро: Вы знаете, есть ли полиномиальный GCD в NC?
T ....
1
@ Арул: да, это так. См. Фон Цур Гатен, Параллельные алгоритмы для алгебраических задач. dx.doi.org/10.1145/800061.808728
Алессандро