Квантовый компьютер.
Квантовый компьютер — вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе классической механики. Полномасштабный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики. Ограниченные квантовые компьютеры уже построены; элементы квантовых компьютеров могут применяться для повышения эффективности вычислений уже на существующей приборной базе.
Куби́т (q-бит, кьюбит; от quantum bit) — квантовый разряд или наименьший элемент для хранения информации в квантовом компьютере .
Как
и бит,
кубит допускает два собственных
состояния, обозначаемых 
и 
,
но при этом может находиться и в
их суперпозиции,
то есть в состоянии:
,
|A|2+|B|2=1
где 
и 
любые комплексные
числа,
удовлетворяющие условию 
.
При
любом измерении состояния кубита он
случайно переходит в одно из своих
собственных состояний. Вероятности
перехода в эти состояния равны,
соответственно 
и 
,
то есть косвенно, по наблюдениям за
множеством кубитов, мы всё-таки можем
судить об исходном состоянии.
Кубиты могут быть связаны друг с другом, то есть, на них может быть наложена ненаблюдаемая связь, выражающаяся в том, что при всяком измерении над одним из нескольких кубитов, остальные меняются согласованно с ним. То есть, совокупность запутанных между собой кубитов может интерпретироваться как заполненный квантовый регистр. Как и отдельный кубит, квантовый регистр гораздо более информативен. Он может находиться не только во всевозможных комбинациях составляющих его битов, но и реализовывать всевозможные тонкие зависимости между ними.
Несмотря на то, что мы сами не можем непосредственно наблюдать состояние кубитов и квантовых регистров во всей полноте, между собой они могут обмениваться своим состоянием и могут его преобразовывать. Тогда есть возможность создать компьютер, способный к параллельным вычислениям на уровне своего физического устройства и проблемой остаётся лишь прочитать конечный результат вычислений.
Вычисление
Упрощённая схема вычисления на квантовом компьютеревыглядит так: берется системакубитов, на которой записывается начальное состояние. Затем состояние системы или её подсистем изменяется посредствомунитарных преобразований, выполняющих те или иныелогические операции. В конце измеряется значение, и это результат работы компьютера. Роль проводов классическогокомпьютераиграюткубиты, а роль логических блоков классического компьютера играютунитарные преобразования. Такая концепция квантового процессора и квантовых логических вентилей была предложена в1989 годуДэвидом Дойчем. Также Дэвид Дойч в1995 годунашёл универсальный логический блок, с помощью которого можно выполнять любые квантовые вычисления.
Оказывается, что для построения любого вычисления достаточно двух базовых операций. Квантовая система дает результат, только с некоторой вероятностью являющийся правильным. Но за счет небольшого увеличения операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице.
С помощью базовых квантовых операций можно симулировать работу обычных логических элементов, из которых сделаны обычные компьютеры. Поэтому любую задачу, которая решена сейчас, квантовый компьютер решит, и почти за такое же время. Следовательно, новая схема вычислений будет не слабее нынешней.
Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2n базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически (квантовый) алгоритм Гроверапоиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов