Допоміжний біт

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Допоміжні біти — це деякі додаткові біти, які використовуються для досягнення певних цілей в обчисленні (наприклад, оборотне обчислення). У класичних обчисленнях будь-який біт пам'яті можна вмикати або вимикати за бажанням, не вимагаючи попередніх знань або додаткових пристосувань. Однак це не так у квантових обчисленнях або класичних оборотних обчисленнях. У цих моделях обчислень всі операції над пам'яттю комп'ютера повинні бути оборотними, а через вмикання та вимикання втрачається інформація про початковий значення цього біта. З цієї причини в квантовому алгоритмі неможливо детерміновано встановити біти в конкретний прописаний стан, якщо тільки йому не надано доступ до бітів, початковий стан яких відомий заздалегідь. Такі біти, значення яких відомі «апріорі», відомі як «біти допоміжних елементів» у квантових або оборотних обчислювальних завданнях[en].

Використання трьох допоміжних бітів та чотирьох вентилів Тоффолі для побудови вентиля НЕ з 5 елементами керування. Допоміжні біти в кінцевому підсумку потрапляють у сміття, оскільки ефекти на них не були необчислюваними.

Тривіальне використання допоміжних бітів зменшує складні квантові вентилі до простих. Наприклад, розмістивши входи керування на допоміжних бітах, вентиль Тоффолі можна використовувати як CNOT або вентиль НЕ.[1]

Для класичних оборотних обчислень відомо, що один допоміжний біт необхідний і достатній для універсального обчислення.[2] Допоміжні біти не обов'язкові, але додатковий робочий простір може дозволити більш прості схеми конструкцій, які використовують менше вентилів.[1]

У квантових обчисленнях, квантовому каталізі[en] допоміжні кубіти використовуються для зберігання заплутаних станів, які дають змогу виконувати завдання, які зазвичай неможливі за допомогою локальних операцій та класичної комунікації.[3] Квантові комп'ютери також використовують допоміжні біти для квантової корекції помилок.[4]

Примітки[ред. | ред. код]

  1. а б Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (вид. 2nd). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. 
  2. Aaronson, Scott; Grier, Daniel; Schaeffer, Luke (2015). «The Classification of Reversible Bit Operations». arXiv:1504.05155 [quant-ph]. 
  3. Azuma, Koji; Koashi, Masato; Imoto, Nobuyuki (2008). «Quantum catalysis of information». arXiv:0804.2426 [quant-ph]. 
  4. Shor, Peter W. (1 October 1995). Scheme for reducing decoherence in quantum computer memory. Physical Review A 52 (4): R2493–R2496. Bibcode:1995PhRvA..52.2493S. PMID 9912632. doi:10.1103/PhysRevA.52.R2493. Процитовано 6 June 2015.