Теоретически квантовые компьютеры будут способны быстро решать задачи, на которые у суперкомпьютеров уходили бы тысячи лет. Эта технология может изменить привычный нам мир. Популярно о квантовых компьютерах рассказывает Евгений Глушко в очередном выпуске на канале наших друзей Sci-One TV. Текстовую версию — как и всегда — читайте под катом.
Обычному пользователю квантовый компьютер ещё долго будет не нужен, может быть даже никогда. Но с его помощью уже сегодня можно поставить на колени всё и всех, кто зависит от интернета: например, мировые банки и любые современные финансовые системы. Ну или просто можно узнать всё, что от вас пытаются скрыть другие люди.
В 90-х годах прошлого века американский математик Питер Шор придумал квантовый алгоритм, который способен очень быстро разложить большущее число на два простых сомножителя. Казалось бы, кому это вообще надо? К сожалению, обычные компьютеры (как и суперкомпьютеры) справляются с этой задачей из рук вон плохо. Т.е. разложить число 15 в произведение 3*5 они могут, а вот если в числе 100 или 1000 знаков, то уже не очень. Чисто технически они могут это сделать — просто переберут все комбинации, но на это уйдёт не один миллион лет. И эту слабость классических компьютеров используют современные криптографические алгоритмы. На сегодняшний день практически вся ценная информация, которая передаётся через интернет, зашифрована с таким расчётом. Это и банковские транзакции, и секретные переговоры, и даже ваша переписка в социальных сетях. Расшифровать всё это с помощью классических компьютеров практически нереально. Теперь представьте, что кто-то вдруг создал квантовый компьютер и запустил на нём алгоритм Шора. И тогда любая зашифрованная в мире информация станет для него доступна.
Но этому можно помешать. Например, с помощью квантовой криптографии, когда информация зашифровывается в квантовое состояние отдельных фотонов. Так что вам будет не обойтись без квантового компьютера. А квантовый компьютер невозможен без кубитов. Кубиты — квантовые биты — такие же элементарные блоки квантового процессора, как транзисторы в процессорах обычных компьютеров. Нужно различать теоретическое понятие кубита, как единицы квантовой информации, и физическое воплощение кубитов, для которого могут быть использованы различные физические системы — фотоны, ионы, спины ядер и электронов. Сегодня больше всего надежд возлагается на сверхпроводящие кубиты.
Но как работает кубит? Всем нам знакомы биты — нули и единички, которые обрабатываются обычными компьютерами. Квантовые биты очень на них похожи (хотя и не без квантовых странностей). У них тоже есть два основных состояния — 0 и 1, но, благодаря особому квантовому свойству — суперпозиции — они могут находиться в любом из состояний между нулем и единичкой.
Суперпозиция наглядно показана в знаменитом мысленном эксперименте с котом Шрёдингера: кот в закрытом ящике одновременно и жив, и мёртв, пока мы не откроем крышку и не посмотрим на него. Так же и с кубитами — они могут находиться в произвольном состоянии между нулём и единицей. Но когда мы измерим их, то всегда с определённой вероятностью получим либо 0, либо 1.
Кстати, кубиты были одной из любимых тем Фейнмана! В 1980-х годах он предложил использовать существующие в природе квантовые системы с двумя состояниями (двухуровневые системы), чтобы симулировать сложные для классических компьютеров задачи. Правда, сам он не знал слово «кубит» — оно было придумано чуть позже Стивеном Визнером. А кубит Визнер придумал для обозначения квантовых денег.
Как создать кубиты? Уже предложено множество разных решений: квантовые точки, захваченные ионы, дефектные алмазы, фотоны и, конечно же, сверхпроводящие схемы, которыми занимаемся мы с коллегами. И нам удалось создать первый в России сверхпроводящий кубит. Достоинства такого типа кубитов очевидны — это большие квантовые объекты, которые можно спокойно поместить на чип и не беспокоиться, что они куда-то улетят, подобно атомам или ионам. Их можно размещать как угодно и в каком угодно количестве, а также точно контролировать их параметры. Подобная искусственная квантовая система — наиболее вероятный кандидат для построения квантового компьютера. А ещё сверхпроводящие кубиты очень похожи на существующие процессоры, поэтому не составит большого труда наладить их полномасштабное производство.
Сверхпроводящий кубит — это просто кольцо из сверхпроводника (металла, по которому электрический ток может течь без потерь). Но можно заметить и несколько особенностей. Они называются джозефсоновскими переходами и представляют собой два кусочка сверхпроводника, разделенных тонкой прослойкой изолятора. Пары электронов могут без проблем проникать через эту прослойку благодаря квантовому туннелированию. Благодаря джозефсоновским переходам мы можем управлять энергетическими уровнями в наших кубитах, подстраивая их необходимым образом. К примеру, когда ток в кольце течёт по часовой стрелке, кубит находится в состоянии 0, а когда против часовой — в состоянии 1. Но и это всё в теории. Как же практически создать такие структуры? Здесь на помощь приходит электронная литография — рисование пучком электронов по чувствительной поверхности. Таким способом можно создавать невероятно маленькие структуры размером вплоть до 10 нанометров!
Когда нужная структура нарисована, на поверхность чипа напыляется металл (например, алюминий). И сверхпроводящий кубит готов! Потом его нужно измерить. Для этого мы помещаем чип в большой криостат. Это тот же холодильник, только очень дорогой и работающий на смеси жидкого гелия. Он позволяет получать крайне низкие температуры — вплоть до одной сотой градуса выше абсолютного нуля! Это в сто раз холоднее, чем в самом холодном месте во Вселенной! Зачем нужны такие низкие температуры? Во-первых, чтобы сверхпроводники, из которых сделан наш чип, начали сверхпроводить — чтобы электроны объединились в пары и стали двигаться согласованно и без потерь энергии. Во-вторых, чтобы максимально изолировать нашу хрупкую квантовую систему от внешнего мира. В первую очередь — от теплового шума — злейшего врага любой «квантовости».
Собственно, это одна из проблем, из-за которой до сих пор не удалось создать настоящий полноценный квантовый компьютер. Вы, наверное, слышали, что компания IBM объявила о наступившей эре квантовых компьютеров и даже дала всем желающим доступ к одному такому через интернет. Но это пока больше реклама, хотя и основанная на серьёзной научной работе. Правда в том, что инженеры IBM собрали процессор всего из 5 кубитов, на котором ничего серьёзного запустить нельзя (для этого их нужно несколько сотен). Хрупкость кубитов мешает нам вступить в новую эру. А когда их соединяют вместе, время жизни кубитов стремительно уменьшается.
Происходит это потому, что кубиты — хрупкие квантовые системы, которые желательно максимально изолировать от окружающего мира (тогда они смогут сохранять своё квантовое состояние). А когда рядом с ними мы сажаем ещё кубиты, они неизбежно начинают взаимодействовать друг с другом, и квантовое состояние каждого из них разрушается. И чем больше их будет рядом — тем быстрее оно будет разрушаться.
Любители компьютерных игр наверняка спросят: и столько сил ради компьютера, на котором даже Доту или Майнкрафт не запустить? Про шифрование я уже говорил. Но важно и другое. Создав квантовый компьютер, мы сможем выиграть в скорости решения пусть всего нескольких, но крайне важных для современной цивилизации видов задач:
- быстрый поиск по гигантским базам данных (а их становится всё больше);
- оптимизация грузоперевозок (задача коммивояжёра);
- ускорение и удешевление поиска новых лекарств и материалов, например, высокотемпературных сверхпроводников.
Но впереди ещё много работы. Да пребудет с вами наука!
Полезные ссылки:
makeitquantum.ru — для дальнейшего чтения по теме.
vk.com/makeitquantum — свежие квантовые новости.
mipt.ru/science/labs/artificial_quantum_systems_lab — лаборатория Искусственных квантовых систем.
Комментарии (99)
TerraV
04.07.2016 17:25Я наверное тупой, но сколько не размышлял, так и не смог понять идею с котом Шрёдингера.
vilgeforce
04.07.2016 17:41+3Идея как раз в том, что нельзя переносить законы квантовой механики в макромир.
Zenitchik
04.07.2016 17:48+1А Шредингер-то хотел этим примером показать, что в квантовой теории что-то не так.
vilgeforce
04.07.2016 17:49+1«которым он хотел показать неполноту квантовой механики при переходе от субатомных систем к макроскопическим.»
isbcc
04.07.2016 17:53тоже не очень понимаю. Там вроде атом цезия с известным периодом полураспада. То есть состояние кота зависит от времени. Как только закрыли кота, велика вероятность, что он еще жив, и наоборот, через много времени вероятность что мертв больше. Или что-то не понимаю?*
Alex27398
04.07.2016 20:29+3Период полураспада хорошо работает с огромной кучей атомов, а единственный атом может существовать ну оочень долго и никто не может определить, когда он распадётся.
Вроде, так.Temtaime
04.07.2016 21:36-8Просто ещё не научились определять, когда же он распадётся.
Вообще вся современная физика — костыль на костыле.Temtaime
05.07.2016 11:28-4О, у кого-то бомбануло.
Это просто констатация факта.
Я — программист, а не физик. Так что с этой проблемой разберутся физики через пару десятков лет сами.)
Xaliuss
05.07.2016 13:54+1Физическая модель позволяет построить закон распределения для времени распада, который соотносится с реальными данными. Из чего и следует невозможность точного определения времени распада. Период полураспада — срок времени, который даёт вероятность распада 1/2 и является статистической характеристикой.
VenomBlood
06.07.2016 04:05Ну вообще, если говорить формально — принцип скрытых локальных переменных определяющих распад ядра (или нейтрона, если упростить задачу) кажется достаточно чудным (и я бы сказал — не очень ложащимся в дух существующей квантовой теории), но я не в курсе чтобы существовал какой либо эксперимент, позволяющий их исключить, что уж говорить о скрытых нелокальных переменных.
Физические модели не говорят о том, является ли процесс распада истинно случайным (два абсолютно идентичных ядра не факт что распдутся одновременно) или завязан на локальных параметрах (например в момент образования ядра происходят процессы, определяющие значение скрытого параметра, который ответственнен за точное время распада).
Shkaff
06.07.2016 10:10-1FYI Неравенства Белла давно продемонстрированы экспериментально, так что про локальных, конечно, нет.
VenomBlood
06.07.2016 10:16Я вот думал при написании — стоит ли пояснить про неравенство Белла, ведь найдется же уникум который увидит два слова и вставит не к месту.
Нашелся.
Неравенство Белла показывает отсутствие скрытых локальных переменных для квантовой запутанности. К его доказательству до сих пор есть вопросы, но склоняются конечно к тому что оно все же нарушается. Но к распаду это какое отношение имеет?Shkaff
06.07.2016 11:02Это хороший вопрос, но мне кажется, что было бы странно, если бы существовали локальный переменные, которые влияют на одни вероятностные процессы в квантовой механике, но не на другие. В конце концов, что распад ядра, что запутанность описываются одними и теми же уравнениями. Поэтому если мы можем с уверенностью сказать, что неравенства Белла нарушаются для запутанности (а мы все же можем, практически все loopholes закрыты уже), то почему они не должны нарушаться в более простых процессах (где скрытые переменные даже и не добавляют ничего к пониманию).
VenomBlood
06.07.2016 11:14Да. Это именно то что я имел ввиду. С точки зрения текущего понимания теории — вроде подобные локальные переменные выглядят странно, но с формальной точки зрения я не нашел фундаментального обоснования. В квантовой теории иногда появляются такие выходящие за рамки бытовой логики и прошлых теорий вещи, что я допускаю возможность любых чудных поворотов в том как это на самом деле работает.
Кстати, есть интересная гипотеза о локальных «вешних» переменных вызывающих распад (в книжке это тоже относят к «локальным переменным»). Объясняется это тем что квантовые флуктуации пространства/вакуума в области нахождения частицы и являются тем триггером, который вызывает распад. Если подобные флуктуации окажется что на деле не флуктуации, к являются возмущениями неизвестного поля(к примеру) и могут быть рассчитаны — то мы можем рассчитать точное время распада каждого атома.
В целом я склоняюсь что локальных переменных нету.Shkaff
06.07.2016 11:34Мне кажется, тут есть некоторая неточность в термине «скрытые переменные». Обычно он относится к процессу измерения — мы не пониманием, почему происходит коллапс волновой функции, и как объяснить ЭПР парадокс, и вот придумываем скрытые переменные. В случайных же процессах нет нужды в таких скрытых переменных. Случайный процесс — дело обычное, и распад в этом смысле — «классический» процесс. То бишь, в нем нет никакой квантовой «странности», по сравнению с измерением запутанных частиц. Поэтому если и существует такая теория скрытых переменных, которая не проявляется для запутанных частиц, а только приводит к распаду ядра — она неотличима от «обычной» физики, и не принесет ничего нового к объяснению странностей квантов.
VenomBlood
06.07.2016 11:50Может проблема в терминологии. Та которая мне встречалась говорит о скрытых переменных как о переменных на принципиально ином уровне нежели обсуждаемая система — как, например, спины отдельных частиц в куске хлеба. Это не подразумевали принципиальной невозможности измерения подобных параметров. В этом случае открытие локальных внутренних скрытых параметров определяющих распад позволят, возможно (если измерение неразрушающее), предсказать распад каждой конкретной частицы.
Shkaff
06.07.2016 12:02Вот тут в чем дело: если рассматривать систему квантовомеханически, то каждый атом находится в состоянии суперпозиции распался — не распался. Для бета распада, например, это значит, что система (бета частица — остальное ядро) является запутанной. А для запутанной системы неравенства Белла должны нарушаться, что было экспериментально доказано. Поскольку наше измерение — это наблюдение бета частицы, то это измерение производит коллапс состояния ядра в «распалось». Именно для таких процессов были придуманы неравенства Белла.
Xaliuss
06.07.2016 11:29+1Имхо принцип, который применили для неравенства Белла, работает и для распада (в ссылке выше сказано, что теорема Белла применима к любым физическим характеристикам квантовой частицы, а ядро и время его распада туда подходит). Никаких статистических отклонений для распада не зафиксировано, значит наличие большого класса локальных переменных можно исключить сразу, а остальные, даже при их наличии, могут оказаться принципиально не наблюдаемыми (эксперименты никак не могут определить их наличие или значения, подчиняясь только принципам тервера).
Авторы полагают, что их эксперимент опровергает большой класс детерминистических теорий, оставляя только такие, которые практически невозможно ни подтвердить, ни опровергнуть экспериментально, а именно, теории, позволяющее путешествовать во времени в прошлое и производить там действия, а также теории «суперреализма», согласно которым далёкое общее прошлое до возникновения запутанной пары заранее определяет как её поведение, так и все скрытые переменные, связанные с её детектированием.
Эта цитата применима и к распаду. Путешествия во времени могут проверить детерминированность, но без этого модель проще без скрытых переменных, когда два разных ядра одного изотопа принципиально ничем друг от не отличаются.VenomBlood
06.07.2016 11:40Неравенство Белла говорит о том что не существует квантовой теории которая объясняла бы все явления скрытыми переменными, разве не так? (Английская версия статьи на Вики более доходчива, советую). Из этого не следует автоматическое опровержение локальных переменных для распада. Хотя, соглашусь, подобное объяснение выглядело бы чудно.
VenomBlood
06.07.2016 10:43+2Михаил, вне зависимости от того прав я или нет — вы меня извините за резкий тон. Вы без наезда, а меня что то дернуло.
Varkus
04.07.2016 18:03-4— Кот жив(1) или мёртв(0)?
— Он жив на столько же на сколько мёртв (суперпозиция).
Существование Бога тоже в суперпозиции — его не существует на столько же на сколько он существует, потому что не доказано ни то ни другое.Roboserv
05.07.2016 10:34Матчасть подсказывает, что доказать отсутствие не возможно. Это не значит, что нужно верить в летающих пони, вампиров, единорогов и летающего макаронного монстра в купе с чайником Рассела. Матчасть!
eugzol
05.07.2016 13:19Большой взрыв, Тёмную материю,…
VenomBlood
06.07.2016 04:07Большой взрыв — фальсифицируемая гипотеза. Темная материя — вообще термин для «нечто» которое приводит к наблюдениям отличным от предсказаний классических (на момент обнаружения) теорий не учитывающих, соответственно, это «нечто».
eugzol
06.07.2016 11:37> Большой взрыв — фальсифицируемая гипотеза
Это интересное утверждение. А не подскажите авторитетные источники, обосновывающие этот тезис?
> Темная материя — вообще термин для «нечто» которое приводит к наблюдениям отличным от предсказаний классических (на момент обнаружения) теорий не учитывающих, соответственно, это «нечто».
Ну, а это уже очень похоже на определение того, как люди используют слово «Бог», сами подумайте :)VenomBlood
06.07.2016 11:57Ну например если бы небыло микроволнового излучения, вселенная бы не расширялась, мы бы получили доказательство негомогенности и неизотропности вселенной на любых масштабах и так далее. Это достаточно очевидные вещи. Посмотрите Вики статью. Там есть достаточно описания, показывавшего что теория большого взрыва фальсифицируема.
Varkus
06.07.2016 12:59Однажды Альберт Эйнштейн спросил своего друга Нильса Бора:
— Ты веришь, что Луны нет, когда мы на неё не смотрим?
На что Бор отверил:
— А ты можешь доказать обратное?
«Этим двум никчёмных тёмным людишкам нужно к психиатру сходить» — Вы так думаете?Roboserv
06.07.2016 13:36-1Ты так и не понял. Давай я попробую еще раз:
Доказать отсутствие того, чего не существует — не возможно. Это не значит, что нужно верить в летающих пони, вампиров, единорогов и летающего макаронного монстра в купе с чайником Рассела.
И загугли уже наконец чайник Рассела.Varkus
06.07.2016 14:16Нет, это ты не понял.
Как можно утверждать «НЕ ВОЗМОЖНО»?
Что мешает генной инженерии пони отрастить крылья достаточного размера для полёта?
Что мешает биоинженерам создать вирус синтезирующий в зараженном человеке гены клыков и неутолимой жажды крови и остальные атрибуты вампиров?
Тоже касается единирога.
Вот с макаронным монстром придётся повозиться…
Просто как говорится на вики «чайник Рассела» — ВСЕМУ СВОЁ ВРЕМЯ.
Любой адекватный ученный скажет, что невозможного нет, просто не пришло еще время.
Тоже и с богом, не пришло еще время доказать или опровергнуть его существование.Roboserv
06.07.2016 14:30Я просто скопирую еще раз, пока до тебя дойдет. Я даже выделил нужное слово.
Доказать отсутствие того, чего _не_существует_ — не возможно.
Varkus
06.07.2016 18:33Взял с полки баночку и протёр лоб фэйспалмовым маслом.
Кто сказал, что не_существует? Да кто бы он не был, это человек, а ВСЕ люди ошибаются.
Математиками и физиками доказана невозможность существования радиоволн квадратной формы.
И если вы не верите математикам и физикам, потому что они люди, можете всегда сами проверить это утверждение!Roboserv
06.07.2016 19:31Здравый смысл подсказывает не верить в розовых летающих пони т.к. нету ни доказательств ни логического объяснения.
У вас реальные проблемы с пониманием устройства мира или выяснения правды. Загуглите научный метод, здравый смысл и рациональное мышление. Я устал тратить на тебя свое время в очевидных вещах.
Можешь и дальше верить в деда мороза, вампиров, летающий чайник, бога, приведения и тп, ибо доказать их отсутсвие невозможно. Походу ты этого никак не поймешь. Удачи жить в фантазиях.
taujavarob
06.07.2016 20:26Roboserv > Доказать отсутствие того, чего _не_существует_ — не возможно.
Это просто. Просто перебираем всё множество. Оно конечно. И доказываем.Varkus
10.07.2016 08:41Не соглашусь с Вами, когда-то пределом множества объяснений было «Солнце вращается вокруг земли, потому-что..», из той же оперы гравитация и прочие явления, чью природу не возможно было раскрыть на тот момент.
Qu3st
09.07.2016 14:54Абсолютно согласен с предыдушем комментарием. Если система конечна, то доказать отсутсвие чего-либо можно перебором всего, что есть. Если система бесконечна, то смысла доказывать, что в ней чего-то нет — нет, ведб в ней должно быть всё.
Varkus
10.07.2016 08:29+100500 с Вами согласен!
Не доказано, что система конечна или бесконечна, а значит остаётся перебирать варианты, пока что-нибудь не докажут :)taujavarob
12.07.2016 17:51Varkus > Не доказано, что система конечна или бесконечна
Стоп! — Доказано что число атомов во Вселенной конечно. И даже подсчитано примерно чему равно.
Так что — система конечна — Перебираем всё множество. Оно конечно. И доказываем.Mad__Max
12.07.2016 21:31+1Количество в видимой (причем видимой конкретно сейчас) вселенной.
А о ее реальных (полных) размах и конечны они или нет вообще есть только пачка разных гипотез, которые никак не проверить.
taujavarob
12.07.2016 22:24-1«Mad__Max > А о ее реальных (полных) размах и конечны они или нет вообще есть только пачка разных гипотез, которые никак не проверить.
Итан писал недавно — протоном больше и Вселенная в чёрную дыру. Протоном меньше и Вселенная в полный разброс (инфляция не остановилась бы).
Так что — система конечна — Перебираем всё множество. Оно конечно. И доказываем.Shkaff
13.07.2016 00:09+1Цитировать Итана в научных спорах… нда… вы бы еще пост на однокласниках предложили в качестве довода.
taujavarob
13.07.2016 19:25-2Shkaff > Цитировать Итана в научных спорах… нда… вы бы еще пост на однокласниках предложили в качестве довода.
Вы часом сайт не попутали? — Итан вещает на geektimes.ru
И вы сейчас на geektimes.ru в коментах.
Shkaff
13.07.2016 19:29+2Итан, при всем уважении как к ученому, вещает порой невообразимую желтизну и отсебятину, которая не подтверждена никакими источниками. Он делает хорошее дело для популяризации, но частенько переходит границы, что делает его исключительно ненадежным подкреплением аргументов.
taujavarob
13.07.2016 20:28-1Shkaff > Он делает хорошее дело для популяризации, но частенько переходит границы, что делает его исключительно ненадежным подкреплением аргументов.
Он вполне надёжен для ссылок в коментах на geektimes.ru
Возможно в диссертации на него и не надо ссылаться, но мы на geektimes.ruShkaff
13.07.2016 20:29+1Вы либо ставите диагноз качеству аудитории на гиктаймс, либо своему пониманию физики.
custos
04.07.2016 18:13+1Известный кот тут упомянут конечно не к месту, суперпозиция в кубите важна, но главная особенность заключается в возможности их запутать (в квантовом смысле), что позволит параллельно (условно говоря за один такт) произвести огромный объём вычислений.
fireSparrow
04.07.2016 22:04+5«Шрёдингер ходил по комнате в поисках нагадившего котёнка, а тот сидел в коробке ни жив, ни мертв.»
Shkaff
04.07.2016 17:52Любопытно, а можно ли вообще сказать, что квантовый компьютер непременно быстрее обычного? С глупым перебором — конечно, да… А вот есть ли доказательство, что не существует алгоритма на классическом компьютере, который будет сравним с квантовым?
Varkus
04.07.2016 18:11-1Однозначно быстрее:
— в электронике информация переносится электронами с конечной скоростью, которую уже давно посчитали. На сколько помню она чуть меньше световой скорости.
— в квантовой «электронике» информация передаётся квантами существующими одновременно во всех точках вселенной.
на сколько я знаю, так и не смогли посчитать скорость передачи информации между «связанными» частицами.
https://ru.wikipedia.org/wiki/Квантовая_запутанностьShkaff
04.07.2016 18:14+4Да ну, что вы. Во-первых, не электронами, а ЭМ полем, ведь скорость электронов вообще мизерная — сантиметры в секунду. Во-вторых, между связанными частицами информация не передается. В-третьих, речь идет о пределах эффективности. Теоретически может ли классический алгоритм быть сравним с квантовым.
maxzhurkin
04.07.2016 18:20+1Он не быстрее, он МЕГАПАРАЛЛЕЛЬНЕЕ, то есть кубиты устроены так, что на выходе есть информация о всех вариантах развития событий, как если бы обычный компьютер работал одновременно со всеми вариантами исходных данных и выдавал бы вместо просто результата все результаты одновременно, но так, чтобы их можно было отделить друг от друга совершенно не напрягаясь и даже не имея докторской степени. Всё здесь мною сказанное является исключительно моим частным мнением и претендует на правоту не в большей степени, чем выделение газа в резервуар жидкости.
Shkaff
04.07.2016 18:26Ну, по сути мы имеем вместо одного бита (1, 0) один кубит (много состояний). Так что даже не в параллельности дело, а в большем количестве информации в одном кубите. Но операции над кубитами все равно линейные (унитарные). Меня интересует алгоритмическая сложность выполнения операций. Скажем, данный квантовый алгоритм производит операцию за линейное время О(n). Есть ли строгое доказательство, что не существует классического алгоритма с той же эффективностью.
Kobalt_x
04.07.2016 18:45Такого вроде нет. Есть другое: множество задач на которых можно получить экспоненциальное ускорение на КК имеет меру 0. Классической информации в 1 незапутанном кубите столько же.
Shkaff
04.07.2016 19:00Я понимаю, что существуют задачи, с которыми квантовый компьютер скорее всего справится лучше. Мне было любопытно, есть ли какие-то предпосылки для общего утверждения о потенциальном превосходстве квантового компьютера над классическим в любой задаче (доступной квантовому компьютеру) в смысле алгоритмической сложности.
Kobalt_x
05.07.2016 05:55+1Про экспоненциальное ускорение писал выше(таких задач очень мало). На обычных задачах с внешним оракулом, нет замеделения, т.к алгоритм Гровера(точнее есть ускорение по кол-ву обращений к оракулу в \sqrt{2} раза). Большинство алгоритмов описано здесь http://math.nist.gov/quantum/zoo/
maxzhurkin
04.07.2016 18:46Много? Не много, а ВСЕ, для одного бита всего два, но.
Дело не в количестве информации: если бы дело было в количестве, разница легко бы нивелировалась увеличением количества бит.
nikitastaf1996
04.07.2016 18:22-1Ну есть технология и эффективнее и легче.Биокомпьютеры.И вероятность появления у них намного выше.
mphys
04.07.2016 18:48+5Может кто нибудь написать статью не с красивой водой ни о чем, а с примерами «квантовой» арифметики и сравнением её с классической?
EndUser
04.07.2016 23:53Нашёл такое: пояснение факторизации в старой алгебре и пояснение как такой алгоритм критического этапа должен считаться на квантовом компе.
EndUser
05.07.2016 02:00+1(Ссылку ранее съело) http://eax.me/shors-algorithm/
Kobalt_x
05.07.2016 06:31+1Я дико ищвиняюсь, что влезаю. Нов приведённой вами статье используется допущение что мы можем построить сколь угодно большой унитарный оператор. Как правило это не так и a**x mod n нужно реализовывать через одно и двухкубитные преобразования.
Siper
04.07.2016 19:02+1>> «оптимизация грузоперевозок (задача коммивояжёра)»
В отличие от взлома криптографии (где принципиально нет возможности узнать насколько вы близки к правильному ответу), на грузоперевозках идеальный результат будет лишь незначительно лучше, чем полученный отижигом, ГА, и т.п методами. Да быстрее, но для таких задач обычно это непринципиально (то же школьное расписание можно хоть все лето составлять).
perfect_genius
04.07.2016 19:43+4Что я уточнил для себя в последнее время:
-Квантовая телепортация не про перенос объектов.
-Путешествия во времени возможны только в будущее и равносильны «заморозке» себя и «разморозке» в будущем.
-Квантовые компьютеры — не замена обычных ПК, а специализированные, как видеокарты.
Так ведь?
pronvis
06.07.2016 00:08Про путешествие во времени:
На сколько я знаю про прошлое вы правы. Но вот для того чтобы в будущее попасть не обязательно себя замораживать. Нужно просто двигаться со скоростью сильно большей чем тот относительно кого вы хотите двигаться во времени. Так же время течёт быстрее для объектов находящихся возле других объектов с большой гравитацией, звёзды, чёрные дыры.
Где-то было хорошее видео про возможные путешествия во времени — из серии научно познавательных фильмов, но уже не вспомню. Там были вычисления вроде: если мы построим корабль который сможет летать на грани горизонта событий N часов, потом вернётся обратно на Землю, то он вернётся на M дней позже. что-то вроде такого
iChaos
04.07.2016 19:51+3Квантовый компьютер: взлом любого шифра, кубиты и крайне низкие температуры
Возможно придираюсь, но, имхо, заголовок слишком желтушный: квантовые компьютеры страшны прежде всего для асимметричных алгоритмов шифрования, для нормальных симметричных алгоритмов, они гораздо менее страшны…
А для шифра Вернама любой квантовый компьютер страшен настолько же, насколько обычный калькулятор, то есть чуть менее чем никак…
Temmokan
04.07.2016 20:25+1… и хотелось бы заодно у автора статьи узнать, применим ли, например, предел Бремерманна к квантовым компьютерам.
Если применим, то симметричное шифрование с достаточно длинным ключом за разумное время и квантовый компьютер не преодолеет.
Заголовок и общий стиль, действительно, «желтушный». Было бы интересно увидеть больше чисел — например, тщательное, подробное описание того, как сравниваются скорости работы квантового компьютера и компьютера полупроводникового.
Чтобы не возникало ощущения, что всю дорогу сравнивают красное с мягким.Kobalt_x
05.07.2016 06:07+1Не, вот есть у меня куча кубитов, если есть надёжный квантовый канал и возможность запутать их все, то в «идеальных условиях» наращивать кол-во кубитов можно сколь угодно долго. Про шифрование: для длинны в n бит нам всегда понадобится p(n)(полином) даже с учетом коррекциии, а далее гровером перебираем, главное оракул нормально реализовать. Но вообще Симметричное без рассмотрения алгоритма передачи ключа не имеет смысла рассматривать. А алгоритмы передачи ключа через асимметричные криптосистемы ломаются. Так что придётся использовать либо неабелеву классическую криптографии(Без доказательств, что завтра их не сломают). Либо алгоритмы квантового распространения классических ключей, в которых факт прослушки устанавливается моментально.
Temmokan
05.07.2016 07:14Насколько помню, навскидку, тот же NTRUEncrypt квантовыми компьютерами фундаментально быстрее не ломается, так что
> А алгоритмы передачи ключа через асимметричные криптосистемы ломаются.
не всегда верно (про полный перебор не говорим, там нас защитит предел Бремерманна). Поэтому рабочий вариант — передать длинный симметричный ключ (256 бит или больше) посредством NTRUEncrypt или аналога, после чего квантовыми компьютерами уже можно и не пугать.Kobalt_x
05.07.2016 09:21Он не ломается потому что в Svp группа неабелева. Т.е та та самая неабелева криптография, к которой не применим подход через Qft. Про предел не понял. Из определения предела следует только то сто вот этот ящик не может считать быстрее чем что-то если у меня ящиков куча и сильнозапутанные состояния то что мне мешает проводит того же гровера и перебирать? P.S и да состояние меняется быстрее чем за c даже если кубиты в этом состоянии очень далеко.(В теории)
Kobalt_x
05.07.2016 06:23+1Про сравнение скоростей: Скорость выполнения самих операций, пока никто не сравнивает. Просто рассматриваются сложность в худшем случае для известных классических алгоритмов, и сложностные оценки квантовых алгоритмов (количество унитарных преобразований). Для некоторых задач второе число оказывается экспоненциально меньше первого.
Temmokan
05.07.2016 07:20> Скорость выполнения самих операций, пока никто не сравнивает.
Из соображений общего развития было бы интересно увидеть оценки (сравнение скоростей), когда они имеют смысл. Понятно, что в таком случае как минимум нужно гонять один и тот же алгоритм.Kobalt_x
05.07.2016 09:29+1Квантовые алгоритмы сильно отличаются от классических(другая модель вычислений). Так что кроме бенчмарков каких то простых ооператоро и bruteforce vs Grover вряд ли что-то можно сделать
Chudic
04.07.2016 21:42-1Если я правильно понял, квантовый компьютер расшифрует любой шифр почти мгновенно. Но чтобы понять, что он расшифровал, потребуются годы труда обычных компьютеров?
icoz
05.07.2016 00:55-1Нет. Неправильно.
Квантовый компьютер поможет почти мгновенно найти ключ к сообщению. Но только для тех алгоритмов, что построены на факторизации больших чисел.Kobalt_x
05.07.2016 06:15+1Не мгновенно, а экспоненциально быстрее классического компьютера. И не только для факторизации, для дискретного логарифма тоже. Вообще для любой задачи сводящийся к поиску скрытой подгруппы конечной абелевой группы можно экспоненциально быстро найти решение.
QuakeMan
04.07.2016 22:02Меня вот очень давно интересует ответ на вопрос
есть ли доказательство того что в нервных системах происходят «квантовые вычисления»?fireSparrow
04.07.2016 22:14Насколько я знаю — именно для нервных систем пока нет таких наблюдений.
Однако, было показано, что биологические организмы используют на внутриклеточном уровне квантовые эффекты (на примере фотосинтеза растений).
Я думаю, что наличие таких эффектов более чем вероятно в мозгу, и наверняка в процессе эволюции эти эффекты активно участвуют в его функционировании. Но вряд ли они делают там какие-то совсем уж невероятные вещи.QuakeMan
04.07.2016 22:35вопрос как вы наверно догадались имеет отношение к ИИ
вряд ли получится построить полноценный ИИ если окажется что квантовые эффекты являются значимой частью в функционировании мозгаfireSparrow
04.07.2016 22:41Вряд ли для создания сильного ИИ так уж необходимо копировать принцип функционирования биологического мозга.
Впрочем, тут пока слишком много белых пятен и это просто гадание на кофейной гуще.
Mad__Max
06.07.2016 01:47Доказательств такого нет. Есть подобные предположения(гипотезы). Пока не доказанные и ИМХО вообще не особо то обоснованные.
Квантовые эффекты на самых глубинных уровнях конечно есть. Но они вообще везде есть, даже в закипающем на плите чайнике или куске металла лежащего на столе. А вот надежных свидетельств того, что эти мельчайшие эффекты имеют влияние и выходят на вышестоящие макроскопические уровни пока нет.
Скорее есть противоположные свидетельства — что работа нейронов в мозге (и шире — нервной ткани) неплохо защищена от влияния подобного «квантового шума». Например у нейронов есть пороги срабатывания (как четкие пороги по напряжению есть у 0 и 1 в классических компьютерах и мелкие флуктуации напряжения не оказывают никакого влияния на результат вычислений), а например нейромедиаторы выбрасываются дозированными порциями по неск. тысяч молекул за раз(на 1 переданный сигнал), что практически исключает влияние квантовых эффектов имеющих место на масштабах отдельных элементарных частиц и одиночных атомов.Shkaff
06.07.2016 11:10Есть интересная гипотеза, что квантовость в нашем мозгу появляется в спиновых центрах в инонах фософора. Такие центры чрезвычайно устойчивы к декогеренции, и могут сохранять запутанность на временах, достаточных для «вычислений». Более того, он связывает работу нейронов с этими центрами и описывает, как собственно происходит переход информации от запутанных центров к нейронам, и как это может ускорять работу мозга. Самое любопытное, что это единственный элемент, который нам жизненно необходим (это мы знаем из опыта), его очень много в мозгу, и при этом может сохранять квантовые свойства долгое время.
Mad__Max
06.07.2016 23:37+2Да, весьма интересная. Правда в самой научное статье имхо больше «подгонки под результат» и wishful thinking — изначально делается предположение, что в мозгу происходят квантовые вычисления, а потом под это пытается найти хоть какой-нибудь механизм, который не противоречил бы явно известной физике и уже известным данным о работе мозга. Чем какое-то исследование имеющегося явления.
И такой потенциальный механизм в результате нашел. Но там нет ничего о том, что такое на самом деле происходит. Только показано, что в принципе такое может происходить (не запрещено законами физики).
Единственный относительно серьезное свидетельство в пользу такой гипотезы приведено, что эти макромолекулы с центрами из «запутанных» атомов фосфора связанного с кальцием в присутствии ионов лития должны иметь тенденцию замещения кальция на литий, что нарушает работу этой «квантовой машины».
И литий дейсвительно имеет сильное влияние на психику: Препараты лития
Правда там полно обычных (классических) механизмов оказания такого влияния.
А вот зависимость от того, какой именно из изотопов (литий-6 или литий-7) в классических механизмах разницы быть не должно — химические свойства идентичны. Тогда как для «квантовых вычислений» на базе спина ядер разница должна быть существенная. Так что в принципе «протестировать» такую гипотезу можно.
P.S.
Если связь подтвердится — уже представляю желтые заголовки у журналистов: квантовая запутанность вызывает маниакальные психозы и депрессию!
(Препараты лития широко используют для лечения подобных нарушений, будет забавно если выясниться, что это происходит именно за счет того что литий разрушает квантовую запутанность между нейронами).
fireSparrow
04.07.2016 22:20+1«Обычному пользователю квантовый компьютер ещё долго будет не нужен, может быть даже никогда.»
Напомнило:
«Я не вижу никакого смысла в том, чтобы в каждом доме стоял компьютер.» (Кен Олсен, 1977 год)
cursovoy_narod_ru
05.07.2016 10:35-4Обычный компьютер на Маткаде за доли секунды разложил на множители число 2^607-1 (правда, множитель всего один). Это 182 десятичных знака.
Алюминий (а также медь, серебро, золото) не переходят в сверхпроводящее состояние ни при какой температуре! Автор сам не знает, что пишет!
Eol
05.07.2016 17:17+1Да ну, как это — алюминий не сверхпроводник? Критическая температура 1.2К. Источник.
А про медь, серебро и золото автор и не говорил вроде ничего.cursovoy_narod_ru
06.07.2016 21:24Компьютер, работающий при 1 К (а лучше 0,5 К с запасом) — это несерьёзно. Температура жидкого гелия (при атмосферном давлении) намного больше (4 К).
Shkaff
06.07.2016 23:17+1А в чем проблема? Криостаты растворения — это просто и приятно, 20 мК — обычное дело. А также можно парами гелия охлаждать ниже 1К, или адиабатическим размагничиванием (что не очень хорошо для компьютера, правда).
Дома не поставить, конечно, но дома квантовый компьютер и не нужен.
aizzzek
05.07.2016 11:38Может это надо было размещать на сайте mail.ru в разделе хайтек? Там бы прекрасно зашел такой заголовок. А так постквантовые алгоритмы даже не вчера были придуманы.
mtivkov
08.07.2016 19:02кубиты — хрупкие квантовые системы… А когда рядом с ними мы сажаем ещё кубиты, они неизбежно начинают взаимодействовать друг с другом, и квантовое состояние каждого из них разрушается. И чем больше их будет рядом — тем быстрее оно будет разрушаться.
Может в итоге существует теоретический предел на количество соседних кубитов, который не даст сделать большой квантовый компьютер, превосходящий в вычислениях «простые» компьютеры?taujavarob
08.07.2016 22:12+1mtivkov > Может в итоге существует теоретический предел на количество соседних кубитов, который не даст сделать большой квантовый компьютер, превосходящий в вычислениях «простые» компьютеры?
Пока, как я слыхал, нащупывают ПРАКТИЧЕСКИЙ предел. — Ушли недалеко.
vilgeforce
«если в числе 100 или 1000 знаков, то уже не очень.» — не совсем верно. Число в 100 цифр факторизуется за разумное время.
«Чисто технически они могут это сделать — просто переберут все комбинации, но на это уйдёт не один миллион лет.» — давно уже не так. Алгоритмы, более оптимальные чем полный перебор есть. В частности NFS-алгоритмы.
«И тогда любая зашифрованная в мире информация станет для него доступна. » — в общем-то нет. Если кто-то сможет факторизовывать любые числа за разумное время, это не значит, что он вскроет любой шифр.
geisha
Да, обычно упоминают эллиптические кривые, которые, вроде как, не подвержены уязвимости.
«они могут находиться в любом из состояний между нулем и единичкой»
Ну вот не так. Это что, выходит, вместо типа int у нас бит типа float? И как это поможет факторизовать? Зачем вводить неокрепшие умы в заблуждение?
a5b
Эллиптические кривые и задача дискретного логарифмирования ломаются практически тем же самым алгоритмом Шора: http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf "Алгоритм Шора" — Сергей Николенко, Криптография — АФТУ РАН, 2010
Неясно как ломать (не найдены подходящие алгоритмы) асимметричные криптосистемы из группы т.н. постквантовой криптографии, например на решётках (NTRU).
Перебор ключей для симметричных алгоритмов на квантовых компьютерах в теории ускоряется (алгоритм Гровера), но не так эффективно как взлом асимметричных. Гровер снижает сложность ряда атак лишь квадратично, и для защиты от него достаточно увеличить длину ключей в 2 раза:
АНБ не так давно обновляло рекомендации по алгоритмам: https://geektimes.ru/post/260684/
https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml
http://csrc.nist.gov/groups/SMA/ispab/documents/minutes/2015-10/oct21_stanger_final_approved_nsa.pdf "Quantum Resistant Algorithms": "Cryptography Tomorrow Suite… Public Key TBD; Symmetric AES 256; Hash SHA-384"
https://cryptome.org/2016/01/CNSA-Suite-and-Quantum-Computing-FAQ.pdf "Commercial National Security Algorithm Suite and Quantum Computing FAQ", 2016: "The AES-256 and SHA-384 algorithms are symmetric, and believed to be safe from attack by a large quantum computer.… In the area of public key algorithms the future is less clear. One area of general agreement appears to be that the key sizes for these algorithms will be much larger than those used in current algorithms"
https://eprint.iacr.org/2015/1018.pdf "A RIDDLE WRAPPED IN AN ENIGMA" — NEAL KOBLITZ AND ALFRED J. MENEZES
sim3x
Статья полна фраз, которые следует зачеркивать и писать рядом «на самом деле нет»
vilgeforce
Да я дальше даже читать не стал… Факторизация и криптография мне хорошо знакомы, вот и отметил «вкусное».