Анцилла

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Анциллы — это дополнительные биты, используемые для достижения определённых целей при вычислениях (например, в обратимых вычислениях). В классических вычислениях любой бит памяти может быть включен или выключен по желанию, не требуя для этого предварительного знания о состояниях или дополнительных ухищрений. Однако это не относится к квантовым вычислениям или классическим обратимым вычислениям. В этих моделях вычислений все операции с памятью компьютера должны быть обратимыми, а ведь включение или выключение бита приводит к потере информации о его начальном значении. По этой причине в квантовых алгоритмах невозможно детерминированно перевести биты в конкретное желаемое состояние, если только нет доступа к битам, исходное состояние которых известно заранее. Такие биты, значения которых известны априори, известны как биты анциллы в задачах квантового или обратимого вычисления.

Построение вентиля НЕ с пятью управляющими разрядами, с использованием трёх анцилл и четырёх вентилей Тоффоли. Состояние анцилл оказывает неопределённым, потому что оказанное на них влияние не было скомпенсировано обратными вычислениями.

Тривиальное использование анцилл состоит в сведении сложных квантовых вентилей к простым. Например, управляя анциллами, вентили Toffoli можно использовать в качестве вентиля CNOT или НЕ[1]:29.

Для классического обратимого вычисления необходимо и достаточно одного анциллы для полного вычисления.[2] Дополнительные анциллы теоретически не требуются, но могут упрощать схемотехнику[1]:131.

В квантовых вычислениях квантовый катализ использует кубиты анциллы для хранения запутанных состояний, что позволяет выполнять задачи, которые обычно невозможны с локальными операциями и классической связью (LOCC). Квантовые компьютеры также используют анциллы для квантовой коррекции ошибок[3].

Ссылки[править | править код]

  1. 1 2 Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information (англ.) (англ.). — 2nd. — Cambridge: Cambridge University Press, 2010. — ISBN 978-1-107-00217-3.
  2. Aaronson, Scott; Grier, Daniel & Schaeffer (2015), The Classification of Reversible Bit Operations, arΧiv:1504.05155 
  3. Shor, Peter W. Scheme for reducing decoherence in quantum computer memory (англ.) // Physical Review A : journal. — 1995. — 1 October (vol. 52, no. 4). — P. R2493–R2496. — doi:10.1103/PhysRevA.52.R2493. — Bibcode1995PhRvA..52.2493S.