(Извините за несколько дилетантский вопрос)
Я изучал квантовые вычисления с 2004 по 2007 год, но с тех пор я потерял поле зрения. В то время было много ажиотажа и разговоров о том, что КК потенциально может решить все виды проблем, превосходя классические компьютеры, но на практике было только два теоретических прорыва:
- Алгоритм Шора, который показал значительное ускорение, но имел ограниченную применимость и не был действительно полезен вне целочисленной факторизации.
- Алгоритм Гровера, который был применим к более широкой категории задач (поскольку его можно было использовать для решения задач NP-Complete), но который показал только полиномиальное ускорение по сравнению с классическими компьютерами.
Также обсуждался квантовый отжиг, но не было ясно, действительно ли он лучше классического отжига или нет. QC, основанный на измерениях, и представление состояния графов QC также были горячими темами, но на этом фронте также не было доказано ничего определенного.
Был ли достигнут какой-либо прогресс в области квантовых алгоритмов с тех пор? Особенно:
- Были ли по-настоящему новаторские алгоритмы, кроме Гровера и Шора?
- Был ли достигнут какой-либо прогресс в определении отношений BQP с P, BPP и NP?
- Достигли ли мы какого-либо прогресса в понимании природы квантового ускорения, кроме как сказать, что «это должно быть из-за запутанности»?
speedup
grovers-algorithm
shors-algorithm
Алекс Кинман
источник
источник
Ответы:
Это зависит от того, что вы подразумеваете под «действительно новаторским». Гровер и Шор особенно уникальны, потому что они были действительно первыми случаями, которые показали особенно ценные типы ускорения с квантовым компьютером (например, предполагаемое экспоненциальное улучшение для Шора), и у них были убийственные приложения для определенных сообществ.
С тех пор было разработано несколько квантовых алгоритмов, и я думаю, что три заслуживают особого упоминания:
BQP-полный алгоритм оценки полинома Джонса в определенных точках. Я упоминаю об этом, потому что, кроме более очевидных вещей, таких как гамильтоново моделирование, я считаю, что это был первый BQP-полный алгоритм, поэтому он действительно показывает всю мощь квантового компьютера.
Алгоритм HHL для решения линейных уравнений. Это немного забавно, потому что это больше похоже на квантовую подпрограмму с квантовыми входами и выходами. Тем не менее, он также BQP-завершен, и в настоящее время ему уделяется много внимания из-за потенциальных применений в машинном обучении и тому подобном. Я думаю, что это лучший кандидат для действительно новаторского, но это вопрос мнения.
Квантовая химия . Я очень мало знаю об этом, но алгоритмы существенно развились с тех пор, как вы упомянули, и это всегда упоминалось как одно из полезных приложений квантового компьютера.
По сути, нет. Мы знаем, что BQP содержит BPP, и мы не знаем отношения между BQP и NP.
Даже тогда, когда вы изучали его изначально, я бы сказал, что оно было более точно определено. Есть (и были) хорошие сравнения между универсальными наборами затворов (потенциально способными обеспечить экспоненциальное ускорение) и классически смоделированными наборами затворов. Например, напомним, что ворота Клиффорда создают запутанность, но являются классически симулируемыми. Не то, чтобы просто было точно заявить, что требуется в более педагогической манере.
Возможно, где был достигнут некоторый прогресс в терминах других моделей вычислений. Например, модель DQC1 лучше понята - эта модель, кажется, имеет некоторое ускорение по сравнению с классическими алгоритмами, но вряд ли будет способна выполнять BQP-полные вычисления (но прежде чем вы попадете в ажиотаж, который вы можете найти в Интернете , есть это переплетение присутствует в процессе вычислений).
С другой стороны, утверждение типа «это из-за запутанности» все еще не решено полностью. Да, для квантовых вычислений в чистом состоянии должна быть некоторая запутанность, потому что в противном случае систему легко моделировать, но для смешанных разделяемых состояний мы не знаем, могут ли они быть использованы для вычислений или могут быть эффективно смоделированы.
Кроме того, можно попытаться задать более проницательный вопрос: добились ли мы какого-либо прогресса в понимании того, какие проблемы поддаются квантовому ускорению? Это немного отличается, потому что если вы думаете, что квантовый компьютер дает вам новые логические элементы, которых нет у классического компьютера, то очевидно, что для ускорения вы должны использовать эти новые элементы. Однако не ясно, что каждая проблема поддается таким преимуществам. Какие из них? Есть классы проблем, где можно надеяться на ускорение, но я думаю, что это все еще зависит от индивидуальной интуиции. Это, вероятно, еще можно сказать о классических алгоритмах. Вы написали алгоритм х. Есть ли лучшая классическая версия? Может, нет, или, может быть, вы просто не замечаете это. Вот почему мы не знаем, если P = NP.
источник
Алгоритм Керенидис-Пракаш был новаторским, пока Эвин Тан не восстановил почву:
Quanta Magazine: основные достижения в области квантовых вычислений, устаревшие подростком .
источник