Квантовый компьютер, как было уже сказано выше, это некий компьютер, который может использовать в качестве рабочих элементов так называемые Кубиты (Q-bit). Изначально считается что Кубит это некая частица, которая подчиняется законам квантовой механики, то есть, имеет волновую функцию (набор состояний, например ноль и единицу).
Как известно, при добавлении частиц в квантовую систему, количество степеней свободы растет экспоненциально. То есть, один кубит может иметь например 2 состояния, два кубита - четыре, а три кубита - восемь. При этом, система из трех кубитов может одновременно находиться в суперпозиции всех восьми состояний.
Теперь представьте, что вы ищете одно из данных состояний. Особенность квантового компьютера состоит в том, чтобы применяя некие операторы, вы могли менять состояние данной системы. Применение оператора на каждом шаге решения задачи меняет пропорции состояний в общей системе. То есть, вы одновременно тянете за восемь ниток, при этом до последнего шага не знаете какая нитка правильная. Вы можете измерить только один раз.
Шаг за шагом, вы вытягиваете нитку и в определенный момент (для каждого алгоритма есть наиболее вероятный момент, когда система примет состояние, близкое к решению задачи) вы можете "измерить" состояние. При этом, происходит коллапс волновой функции и вы видите ответ (на самом деле, ответ может быть неправильным, но алгоритм должен гарантировать как можно большую вероятность приведения системы в нужное состояние).
Наиболее популярные алгоритмы, например алгоритм Гровера по поиску в неструктурированной базе данных имеют интересные особенности. Так, скажем, Гровер достаточно давно показал, что в базе из N элементов ответ можно найти за SQRT(N) шагов. Например, у вас база 1024 элементов и вы за 32 шага можете найти ответ (без предварительной сортировки). Тем не менее, алгоритм Гровера подразумевает наличие так называемого оператора Оракула. Оператор - Оракул без выдачи ответа на каждом шаге может "тянуть" правильный ответ немного вверх. Смысл и реализация оператора Оракула может зависеть от физической реализации квантового компьютера.
Другой алгоритм, разложения на множители, также справляется с задачей феноменально быстро. При этом, если учесть, что современная криптография в качестве своего базиса имеет алгоритмы, построенные на нахождении множителей, то можно сказать что квантовый компьютер сделает бессмысленным современное шифрование.
Другая, очень обширная область применения квантовых компьютеров может лежать в супербыстрых эмуляторах физических систем, то есть решении разных уравнений квантовой динамики.
Создание квантового компьютера затруднено, потому как систему, состоящую из множества кубитов с физической точки зрения очень сложно создать. Нужно выбрать необходимые материалы, физический принцип, систему управления, которая реализует необходимые операторы, систему измерения. Множество проблем имеют причиной "температурные" шумы.