Все новости от 26 мая 2000 г.

Большой скачок к квантовым компьютерам

Тем, у кого плохая память, поможет квантовый компьютер. Год назад ученые поняли, что при очень специфических условиях электроны можно использовать в качестве супермикропроцессоров. Подобные машины еще далеки от практического применения, но это не помешало Груверу приступить к созданию «квантового ПО». Он разработал алгоритм, позволяющий квантовому компьютеру выполнять поиск в базе данных даже в том случае, если имеется лишь смутное представление о том, что нужно искать.

Природа решает задачи намного эффективнее, чем мы. Вот физики и работают над машинами, способными обуздать эту невероятную мощь, а теперь сделан еще один гигантский шаг в этом направлении. Квантовые компьютеры используют электроны и другие субатомные частицы — q-биты — примерно так же, как микропроцессор использует транзисторные ключи. Однако элементы квантового компьютера намного «умнее», чем классические биты информации. Они могут хранить не только нули и единицы, но и любые промежуточные значения. Это невероятно ускоряет вычисления: там, где обычному компьютеру потребуется миллион шагов, квантовый обойдется, скажем, всего тысячей.

Однако не все так гладко. Квантовые компьютеры нельзя тревожить во время работы. Простого наблюдения за ней достаточно, чтобы нарушить процесс, примерно так же, как просмотр фотопленки во время проявления приводит к порче снимков. Поэтому компьютер работает скрытно, проявляя при этом фантастические способности.

«Пока есть всего несколько квантовых алгоритмов, которые работают лучше, чем классические компьютеры, — говорит директор по исследованиям в области оптической физики Bell Labs Ричард Слашер (Richart Slusher). — Но мы работаем над этим еще не так долго, причем то и дело находим все новые удачные решения». Так что квантовые компьютеры можно сравнить с традиционными вычислительными системами на том этапе их развития, когда полезного ПО было написано очень мало. Пока что в самых интригующих демонстрациях возможностей квантовых компьютеров решается одна из самых сложных, но и прямолинейных математических задач — поиск простых делителей очень большого числа.

Однако в реальной жизни мало задач, заведомо имеющих единственное решение. Правильных ответов чаще всего бывает много — как при поиске веб-страниц, когда ответом служит множество ссылок. «Если вы ищете единственного Джона Смита, машина его найдет. Но если их окажется больше, то для нее это проблема», — говорит Грувер.

Во вторник на научной конференции в Портленде (штат Орегон) Грувер изложил новый алгоритм поиска, который доказывает, что квантовые машины будущего смогут отвечать на неопределенные вопросы с множеством ответов. Это, в сочетании со способностью искать невероятно быстро, сделает квантовые компьютеры мощнейшим инструментом. Пример, который чаще всего приводит Bell Labs: их можно использовать для быстрого определения имени и телефонного номера человека, данные которого вы запомнили лишь частично. «Возможно, вы помните, что его зовут Джон, а фамилия то ли Смит, то ли Джонс, то ли Миллер, — говорит Грувер. — И вы помните также, что последние четыре цифры его телефонного номера такие же, как у вашего врача». Искать такого человека методом классического поиска при помощи грубой вычислительной силы было бы пустой тратой времени. «Но мой новый алгоритм и квантовый компьютер позволят сделать это очень быстро, — продолжает Грувер. — Теперь квантовый поиск работает даже при наличии очень нечеткой исходной информации».

Однако «программное обеспечение» Грувера на действующем квантовом устройстве можно будет испытать не скоро. Его первый алгоритм поиска, позволяющий находить единственный результат, был опубликован в 1996 году; два года спустя он был испытан на первой квантовой машине из четырех q-битов. Сегодня существуют 7-q-битные машины, но до практически полезной размерности они доберутся лишь через несколько лет. Трудно даже предположить, когда появятся 20- или 30-q-битные машины, а это минимальная разрядность, при которой можно начать решать полезные задачи. «Зато есть очень умные люди, которым все это интересно, — говорит Грувер. — Так что можно рассчитывать на то, что дело пойдет ускоренными темпами».

Обсуждение и комментарии

	BOND 26 May 2000 5:23 PM
С ума сдуреть
	vlad vul - vulmail.ru 26 May 2000 5:53 PM
Я найду этого кренделя, Джона Миллера, на обычном компе за 1.5 секунды. Эти квантовые копмпьютеры - чистое надувательство.
	Mr.Life 26 May 2000 5:56 PM
Когда-то и транзисторы некоторые называли надувательством
	Igor 26 May 2000 6:47 PM
Кстати, обратите внимание на поиск простых множителей у числа. Они не пишут в статье, а это же смерть кодированию с открытым ключем.
	Dragon - dragon_uayahoo.com 26 May 2000 6:59 PM
А эти алгоритмы и без того находятся в болезненном состоянии. ведь есть много других интересных математических замков ;)
	Илья 26 May 2000 7:01 PM
Смерть шифрования, когда через N (N>100) лет карманная "квантовая" коробочка за M секунд взломает 256-разрядный ключ Пентагона, положит начало другой эпохе без рынка в его нынешнем виде. В 22 веке людям придется кооперироваться, а не разграничиваться секретами. Предвижу скрытую борьбу вокруг инвестиций и грантов в этой области
	VMF - fritskiyvmf.ssft.net 27 May 2000 1:12 AM
Думаю, что к тому времени будут новые алгоритмы шифрования. Проблема в том, когда же придет время квантовых настольных систем, чувствую что очень не скоро. А как бы хотелось иметь карманный квантовый компьютер в скором времени! Как вам нравится PocketPC c квантовым процессором гигагерц эдак на 500 и памятью эдак терабайт на 800 (про то что это устройство может быть подключенным к интернету на мегабитных скоростях и проч. навороты я вообще и не заикаюсь, так как это само собой разумеется;) по цене $300? Мечта...
	To VMF, Vladimir 27 May 2000 8:22 AM
Да и работать все это будет по Виндами 3000.
	gas - gasland.ru 27 May 2000 11:27 AM
Если хороший квантовый комп может вскрыть 256 битный ключ... то вероятно и самый простой квантовый PC сумеет зашифровать данные с ключем скажем в 10000 бит... причем легко. Ведь ключ можно делать сколь угодно большим, а дело тоьлко в скорости... так что в этой области ничего не измениться...
	Stick - stick109usa.net 27 May 2000 4:09 PM
статью полный дебил написал. "электроны можно использовать в качестве супермикропроцессоров", каково? в каждой строчке какая-нибудь лажа. как только зднету пришло в голову такой спам публиковать.
	Vlad - vobertomcat.ru 29 May 2000 10:25 AM
To Stick. Маразм, конечно. Мысль старая - использовать в качестве ячеек не макро, а микрообъекты, но вся сложность в том, чтобы этими элементами как-то управлять. Ведь даже простейшее АЛУ представляет собой связаную совокупность бистабильных элементов. И не просто связанную, а по по определенному закону. В это вся и сложность. Плюс еще проблема ввода-выводаю
	Garya - hydrocorbina.ru 29 May 2000 11:23 AM
Я читал про отечественные аналогичные разработки. Должен признаться, что понять все это сходу довольно трудно. Само понятие "бит" в теории нечеткой логики не имеет смысла. И даже понятие "алгоритм" как запланированная последовательность действий для нечеткое логики - полная чушь. Возможно, то о чем написано в статье, использует совсем другие подходы, но то, о чем я читал - это революционные технологии, которые могут использоваться в распознавании образов. Идея такая. Поисковый механизм формирует сложную функцию, которую можно представить в виде "кривой лупы" - через нее одни части информации проходят без изменения, другие с изменением, третьи проходят слабо, четвертые не проходят вовсе - причем все это ОДНОВРЕМЕННО (это к вопросу о 1,5 секундах vlad vul). И на выходе вы СРАЗУ получаете результат. То есть, если у вас имеется массив изображений, объемом в 100000 террабайт (грубо говоря, ибо в таких системах они хранятся не в битах/байтах, а в виде вихрей со специфическими характеристиками), то поиск нужного изображения производится накладыванием "кривой лупы" СРАЗУ НА ВЕСЬ МАССИВ - и вы мгновенно получаете искомый результат. Разница в том, что АЛГОРИТМ предполагает ЦИКЛЫ, которые ПЕРЕБИРАЮТ компоненты информации. А в нечеткой логике в обработку передается весь массив СРАЗУ - то есть каждая его частичка взаимодействует с механизмом фильтрации одновременно. В свойствах "лупы" можно задать "похожесть" изображения - в зависимости от этого будет производиться выбор по более или менее строгим критериям. Эти алгоритмы берут свое начало от механизмов распознавания образов мозгом человека - там ведь нет никаких битов и процессоров.
	dimity - ab.c 29 May 2000 11:27 AM
Garya: за 4 года так и несоздав ничего путного, Белл вдруг скакнул на 7-q машина, наверное и туда наши подались ;) Кто-нибудь оригинал читал? Это ж весело: "любые промежуточные значения между 0 и 1", которые хранит квантовый компутер! :)) Тоже рулезная фраза: "Поэтому компьютер работает скрытно, проявляя при этом фантастические способности" наверное в виде фонового квантового излучения :)) Ну и в заключении: "Зато есть очень умные люди, которым все это интересно, — говорит Грувер. — Так что можно рассчитывать на то" что денег ему будут продолжать давать, ведь все равно, кроме него никто в этом не разбирается :)
	Mike - mikeineos.ac.ru 29 May 2000 11:55 AM
К стати, о птичках, ключ длиной 10000 может и не понадобиться. Достаточно иметь ключ, длина которого больше или равна длине сообщения и никакаой супер-супер-супер-квантовый компьютер не поможет. Не взламываются такие ключи принципиально. Короткие ключи применяют, на мой взгляд, по двум причинам. 1- чтобы комп не слишком тормозил 2- чтобы особистам легче работать было.
	david 29 May 2000 3:17 PM
A proshe skazat' vernulis' k razrabotke analogovih mashin, kotoruyu blagopoluchno ostavili let etak 30 nazad...
	Richard 29 May 2000 3:47 PM
Da, vot imenno - vernulis k razrabotkam analogovyh mashin, no tolko na sovsem drugom urovne. I, kstati, eti vse kvantovyje neopredelennosti - veshch dovolno strannaja... ghmz... Posmotrim, chto u nih tut poluchitsa...
	Lamer - lordeltegra.ru 29 May 2000 5:33 PM
Mike А через частотный анализ такой ключ не находится??? :)) На основе нескольких сообщений??
	xla-11 29 May 2000 6:08 PM
Статья - идиотизм. Даже для чела знакомого с темой понять что-либо - невозможно. :) 2 Stick: Гы. А по сути - все верно. Реальный элемент логики - электрон (ион, синглет фотонов). И операции, которые он проводит типа как бы уровня процессора - умножение, деление, сложение. :))) 2 gas: Дело-то как раз не в скорости, а в алгоритме. Хотя по статье этого не понять. :))) 2 dimity: Гм. А так и есть в натуре. Кубит - суперпозиция состояний, скажем на .32 - 0, на .68 - 1. Сведение к "обычному" биту (коллапс) происходит в момент наблюдения (ну, замызганный пример: фотон с поляризацией 45 градусов проходит через горизонтальный поляризатор. Либо пройдет, либо нет - с вероятностью .5. А до того, до момента проверки, его состояние - .5. Не ноль, не единица, а именно половина.). Круче всего то, что кубиты с квантовой системе взаимозависимы, комбинацию из двух кубитов можно рассматривать как вектор на плоскости и любая операция над системой будет дествовать на вектор *целиком*, а не на кубит. Понятно, что при разрядности хотя бы 30-40 кубит обычные системы рядом стоять не будут. 2 Mike. :) С экспонентой или факториалом никогда не сталкивался? :) Вся круть RSA в том, что сложность *очень* быстро растет с длиной ключа, для шифровки - линейно, а для *расшифровки* - экпонента. Поэтому-то для обычного компа, сколько эксагерц не выставляй, этот ключ неподъемен: увеличиваем ключ в десять раз, сложность раскриптовки возрастает в квадриллионы. А для квантового компа просто по самой его идее сложность - логарифм. Поэтому все сегодняшние секурные системы тихо идут курить: какой ключ не ставь, все по хрен, если в реалтайме зашифровали, в реалтайме и расшифруют. На эллипсы надежда. :)
	Boris - b.ignatovmotorola.com 29 May 2000 6:23 PM
Ага ... А если каждое сообщение своим ключем закрыто...
	хla-11 29 May 2000 6:27 PM
2 Mike: Хм. Промазал. Извини, не тебе реплика адресовалась.
	Vit - sensorukrpost.net 3 Jun 2000 7:07 AM
Чтобы получить хороший ответ нужно задать хороший вопрос, ассоциативность в вопросе на сегодняшний день требует огромной разрядности, так что её нечёткой сделать - нужно не 130 IQ, а громадная железяка и много-много программистов с программаторами...
	Polina - polina43hotmail.com 18 Oct 2001 9:17 PM
Chotelos' bi 4ut' podrobnee. V 4e:m sostoit etot algorithm? Kak on rabotaet? ... Esli mne kto-to moshet otvetit' na etot vopros, budu o4en' blagodarna.