Для вопросов по квантовым алгоритмам. То есть алгоритмы, которые теоретически могут быть выполнены квантовыми компьютерами, обычно компьютерами, обеспечивающими «универсальные» квантовые вычисления.
Алгоритм поиска Гровера обеспечивает доказуемое квадратичное ускорение поиска в несортированной базе данных. Алгоритм обычно выражается следующей квантовой схемой: В большинстве представлений важнейшая часть протокола - «врата оракула» UωUωU_\omega , который «волшебным образом» выполняет операцию...
Этот пост от Скотта Ааронсона - очень полезное и простое объяснение алгоритма Шора . Мне интересно, есть ли такое объяснение для второго наиболее известного квантового алгоритма: алгоритм Гровера для поиска в неупорядоченной базе данных размера в O ( √O ( n )O(n)O(n)времяO ( n--√)O(n)O(\sqrt{n}) В...
(Извините за несколько дилетантский вопрос) Я изучал квантовые вычисления с 2004 по 2007 год, но с тех пор я потерял поле зрения. В то время было много ажиотажа и разговоров о том, что КК потенциально может решить все виды проблем, превосходя классические компьютеры, но на практике было только два...
Есть ли общее утверждение о том, какие проблемы можно решить более эффективно с помощью квантовых компьютеров (только модель с квантовыми воротами)? Имеют ли общие проблемы проблемы, для которых сегодня известен алгоритм? Насколько я понимаю, квантовые вычисления помогают с проблемой скрытой...
В последние несколько дней я пытался собрать материал (в основном исследовательские работы), связанный с квантовым машинным обучением и его применениями, для летнего проекта. Вот некоторые из них, которые мне показались интересными (из поверхностного прочтения): Машинное обучение без присмотра на...
Было доказано, что адиабатические квантовые вычисления эквивалентны «стандартным» или квантовым вычислениям модели затвора. Адиабатические вычисления, однако, показывают перспективы для задач оптимизации, где цель состоит в том, чтобы минимизировать (или максимизировать) функцию, которая каким-то...
Квантовые вычисления позволяют нам шифровать информацию другим способом по сравнению с тем, что мы используем сегодня, но квантовые компьютеры намного мощнее современных компьютеров. Итак, если нам удастся построить квантовые компьютеры (следовательно, использовать квантовую криптографию), будут ли...
Ожидается, что алгоритм Шора позволит нам вычислять целые числа, гораздо большие, чем это можно было бы сделать на современных классических компьютерах. В настоящее время учитываются только меньшие целые числа. Например, в этой статье обсуждается разложение .15 = 5 × 315знак равно5×315=5{\times}3...
Фон Недавно я читал статью «Квантовый биткойн: анонимная и распределенная валюта, защищенная теоремой квантовой механики об отсутствии клонирования», в которой демонстрируется, как может функционировать квантовый биткойн. В заключении статьи говорится, что: Квантовые биткойны являются атомными, и в...
Насколько я понимаю, кажется, что есть некоторая уверенность в том, что квантовый отжиг ускорит такие проблемы, как коммивояжер, благодаря эффективности, обеспечиваемой, например, квантовым туннелированием. Однако знаем ли мы, в какой степени предусмотрено...
Хорошо известен результат, что дискретное преобразование Фурье (ДПФ) из N=2nN=2nN=2^n чисел имеет сложность O(n2n)O(n2n)\mathcal O(n2^n) с наилучшим известным алгоритмом при выполнении преобразования Фурье амплитуд квантового состояния с классическим Алгоритм QFT , требует только O(n2)O(n2)\mathcal...
Примечание к словарю: слово «гамильтониан» в этом вопросе используется для обозначения эрмитовых матриц. Алгоритм HHL, по-видимому, является активным объектом исследований в области квантовых вычислений, главным образом потому, что он решает очень важную проблему, которая заключается в поиске...
Глубокое обучение (несколько слоев искусственных нейронных сетей, используемых в контролируемых и неконтролируемых задачах машинного обучения) является невероятно мощным инструментом для решения многих из самых сложных задач машинного обучения: распознавания изображений, распознавания видео,...
Используется алгоритм Гровера, среди прочего, искать нужный пункт yy\mathbf{y} в неупорядоченном списке элементов [x0,x1,...,xn−1][x0,x1,...,xn−1][\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}] длины nnn . Несмотря на то, что здесь есть много вопросов по этой теме, я все еще упускаю суть. Поиск...
В этом ответе объясняется алгоритм Гровера. Объяснение указывает, что алгоритм в значительной степени опирается на оператор диффузии Гровера , но не дает подробных сведений о внутренней работе этого оператора. Вкратце, оператор диффузии Гровера создает «инверсию относительно среднего», чтобы...
Об алгоритме поиска Гровера обычно говорят в терминах поиска помеченной записи в несортированной базе данных. Это естественный формализм, который позволяет применять его непосредственно к поиску решений проблем NP (где хорошее решение легко распознается). Мне было интересно узнать о других...
Во многих работах утверждается, что гамильтоново моделирование является BQP-полным (например, гамильтоново моделирование с почти оптимальной зависимостью от всех параметров и гамильтоново моделирование с помощью кубитизации ). Легко видеть, что гамильтоново моделирование является BQP-сложным,...
На первый взгляд, квантовые алгоритмы имеют мало общего с классическими вычислениями и P против NP, в частности: решение задач из NP с квантовыми компьютерами ничего не говорит нам об отношениях этих классических классов сложности 1 . С другой стороны, «альтернативное описание» классического класса...
Даниэль Санк упомянул в комментарии , отвечая на (мое) мнение, что постоянное ускорение для задачи, допускающей алгоритм полиномиального времени, скудно, что10810810^8 Теория сложности слишком одержима бесконечными пределами масштабирования. В реальной жизни важно то, как быстро вы получите ответ...
В результате превосходного ответа на мой вопрос о квантовой bogosort мне стало интересно, каково современное состояние квантовых алгоритмов сортировки. Чтобы быть точным, сортировка здесь определяется как следующая проблема: Учитывая массив AAA целых чисел (не стесняйтесь выбирать ваше...