поиск по 1171700 познавательным статьям и фото

Показан способ экономии кубитов при квантовых вычислениях

Сотрудники Бристольского университета (Великобритания) сумели провести вычисления по алгоритму Шора, реализованному в условиях строгой экономии кубитов.

Квантовый алгоритм Шора позволяет разложить заданное нечётное составное целое N на простые множители. Чтобы получить ответ, нужно выбрать целое x, которое будет составлять с N пару взаимно простых чисел, не имеющих никаких общих делителей, кроме единицы, а после этого — найти значение порядка r, связывающего x и N таким образом, что xrmod N = 1 (то есть остаток от деления xr на N равен единице). Если порядок установлен, исходная проблема поиска простых множителей становится тривиальной.

Эту последовательность можно представить в виде набора простых классических задач (проверки того, что x и N удовлетворяют условиям, «извлечения» множителей из r) и задачи нахождения порядка, для решения которой требуется квантовый компьютер. Известно, что алгоритм Шора будет работать экспоненциально быстрее, чем лучший из классических алгоритмов разложения на простые множители, и — в перспективе — сделает многие современные схемы криптографической защиты ненадёжными.

При нахождении порядка r традиционным квантовым способом экспериментатору приходится подготавливать две группы кубитов. Минимально допустимая численность первой выражается как log2N; иными словами, здесь должно быть столько кубитов, сколько необходимо для двоичного представления N. Вторая же группа содержит ещё n квантовых разрядов, где n обычно выбирается из интервала log(N2) ≤ n ≤ log(2N2). Для подсчёта общего количества требуемых кубитов, таким образом, можно использовать выражение 3log2N, округляя результат вычислений к большему.

Очевидно, что работать с действительно большими N физики пока не готовы. Экспериментальных методик, которые позволяли бы уверенно контролировать крупные группы кубитов, ещё нет, и возможности алгоритма Шора принято демонстрировать на простейшем примере N = 15. Хотя в начале 2012-го в Physical Review Letters вышла статья, авторы которой утверждали, что им удалось разложить на множители — не по алгоритму Шора — число 143 с применением твердотельных кубитов (спинов ядер водорода в молекуле C6H4ClBr), вопрос о том, носил ли опыт истинно квантовый характер, остаётся открытым. Можно считать, что выше N = 15 при квантовом разложении учёные никогда ранее не забирались.

Опробованный в Бристольском университете вариант реализации алгоритма Шора отличается тем, что упомянутая группа из n кубитов заменяется всего одним кубитом, который используется многократно. Требования к общему числу квантовых битов здесь, следовательно, формулируются уже не как 3log2N, а как log2N + 1. Длительность вычислений при этом возрастает, но схема всё равно остаётся более быстрой, чем любая классическая.

Оригинальная «экономная» методика тестировалась на примере N = 21, x = 4 и r = 3. Интересно, что первую часть выражения log2N + 1 авторы тоже свели к единице, заменив требуемые кубиты одним кутритом (квантовой ячейкой с тремя возможными состояниями). Бережное отношение к ресурсам пошло эксперименту на пользу: в поиске r в итоге участвовали всего два фотона.

Подготовлено по материалам NewScientist и arXiv.


Источник: Compulenta @24.10.2012

Оцените статью:

Теги


Используй свой мобильный - сохрани эту страницe и расскажи о ней друзьям!