Квантовые алгоритмы, основанные на преобразованиях, отличных от преобразований Фурье

19

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

Были ли плодотворные исследования других трансформаций?

Сэм Бервилл
источник
10
Да. И-Кай Лю, Шелби Киммел и другие разработали квантовые алгоритмы, основанные на вейвлет-преобразованиях, а Стивен Джордан разработал квантовые алгоритмы, основанные на преобразовании Клебша-Гордана. Вы можете поискать ссылки в Google, или другие могут прийти, чтобы предоставить некоторые. Конечно, проблемы, решаемые этими алгоритмами, не столь громкие, как факторинг и дискретный журнал (иначе вы бы уже слышали об этом).
Скотт Ааронсон
5
@ScottAaronson комментарий -> ответ
Алессандро Косентино
@ ScottAaronson Отлично, я посмотрю на них. Благодарность!
Сэм Бервилл
Yi-Kai Liu разработал квантовые алгоритмы, использующие кривое преобразование (см. Полную версию на arXiv или короткую версию от FOCS).
Марис Озолс

Ответы:

16

Я хотел бы добавить еще несколько ссылок на комментарий Скотта:

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

  • Преобразования Клебша-Гордана использовались Грегом Купербергом и Одедом Регевым для решения двугранного HSP в субэкспоненциальном (но суперполиномиальном) времени. Эти квантовые алгоритмы не эффективны, но они имеют лучшую сложность запросов, чем классические алгоритмы.

  • Zp2Zp

Я также пишу, чтобы добавить, что мы не должны забывать, что как квантовые преобразования Фурье, так и преобразования Клебша-Гордана не всегда необходимы, даже если они могут быть очень полезными.

  • В алгоритме Шора (или даже в квантово-фазовой оценке) преобразования Фурье могут быть заменены тестами Адамара , поэтому используются только вентили Адамара вместо преобразований Фурье: этот трюк принадлежит Китаеву, и вы можете прочитать об этом здесь .

  • Существует еще один эффективный алгоритм для HSP над Бэкона, Чайлдса, Ван Дама, который не использует преобразования Клебша-Гордана. Вместо этого алгоритм использует определенный тип мощного POVM, известного как довольно хорошее измерение.Zp2Zp

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

Хуан Бермехо Вега
источник
Спасибо что подметил это. Я объяснил аббревиатуру в последнем редактировании.
Хуан Бермехо Вега
4

Не уверен, что это напрямую связано с вашим вопросом, но чтение его заставило меня задуматься о статье Питера Хойера, которую я прочитал несколько лет назад. В нем он показывает, как наиболее популярные квантовые алгоритмы, такие как Гровера или Шора, следуют тому же шаблону применения того, что он называет «сопряженными операторами», и он строит новые алгоритмы, также основанные на этом же шаблоне.

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

http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280

Филипп Ламонтань
источник