А как же оно тикает?
11,301,883 15,067
 

  Dobryаk ( Практикант )
24 сен 2009 23:40:48

Тред №149273

новая дискуссия Дискуссия  414

Цитата: SvK
Есть такой сайт:
здесь
Вроде как квантовый комп презентовали в 2007 г:
тут



Сайт есть. Остался вопрос о содержании... xe-xe..

Магическое слово: кубит. Его реализация на квантовых состояниях пока по настоящему не реализована
Отредактировано: Dobryаk - 01 янв 1970
  • +0.00 / 1
  • АУ
ОТВЕТЫ (16)
 
 
  Fenix ( Слушатель )
25 сен 2009 01:11:35


Спасибо за ответ.
Насколько я понимаю, кроме существования кубита еще и не ясно как на него записать и считать с него информацию
  • +0.00 / 1
  • АУ
 
  Midland ( Слушатель )
25 сен 2009 04:20:51


Вики утверждает что вроде как уже реализовали (http://en.wikipedia.org/wiki/Qubit), в том числе регистр на кубайт (в универе Иннсбрука в 2005). Я сходил по линку на тот Иннсбруковский сайт, так они тоже утверждают что реализовали. И регистр, и несколько других элементов.

Но никакой информации о полном квантовом компьютере таки не видел. Все-таки для компьютера нужно много-много всяких разных элементов, и нужно еще чтобы все это было достаточно стабильным.
  • +0.00 / 1
  • АУ
 
 
  Yura_L ( Слушатель )
27 сен 2009 18:43:41


Много чего читал про эти самые квантовые компьютеры и кубиты, но хоть убей, не понимаю, почему их нужно делать именно на элементарных частицах, используя их квантовые свойства.
Что обычно ругают в обычных меашинах?

1. Что там используют двоичную логику, и что число состояний в кубите больше.
Но если открыть элементарный учебник, то там написано, что что все системы счисления абсолютно равнозначны, и нет такой задачи, которая не решалась бы в двоичной системе, но решалась бы в любой другой. Больше того, как показал тов. Шеннон, наибольшей эффективностью обладает система счисления с основанием, равным е=2.718... а двоичная система немного отличается от оптимальной.  Троичная, правда, эффективней, но в реализации намного сложнее.
И потом, если кому-то надо больше состояний, то например байт может прин7имать 256 состояний. Используйте вместо каждого бита или кубита байт, и этих возможных состояний будет в избытке. Операции с ними задаются логикой АЛУ и могут осуществляться за такт.

2. Что операции с кубитами имеют какие-то волшебные свойства. Чуть выше я сказал уже, что кубит можно заменить, например, байтом с любой логикой АЛУ и будет то же самое.

3. И наконец, что кубиты одновременно находятся во всех состояниях, и квантовый компьютер в принципе выдает стохастическое решение.
Но обычная память с выключенным питанием, тоже, можно сказать, находится во всех состояниях одновременно. И зачем нужно недерминированное решение, я тоже понять не могу при всем желании. Если нужен генератор случайных чисел для стохастических задач, то такие генераторы есть, и для этого не нужны квантовые свойства элементарных частиц.

Вывод: американцы совершенно правильно не выделяют ни цента на эту тематику.
  • +0.00 / 0
  • АУ
 
 
 
  Midland ( Слушатель )
27 сен 2009 20:14:06


Есть определенные типы проблем которые квантовый компьютер может решать несравнимо быстрее чем классический компьютер. В некоторых случаях это обещает большую практическую пользу.

Например, многие современные алгоритмы шифрования (например, алгоритмы используемые в SSL/HTTPS) основаны на трудности разложения числа на простые множители.
Чуть-чуть деталей: любое число n большее чем 1 может быть представлено как n=P1*P2*P3...*Pk, где P - простые числа. Зная последовательность P1,P2...Pk можно легко и быстро вычислить n (просто перемножаем P1,P2...Pk), но зная n вычислить P1,P2...Pk последовательность очень тяжело поскольку надо перебирать все возможные комбинации. Есть несколько алгоритмов которые несколько ускоряют процесс, но все равно это очень долго.

Фишка в том что квантовый компьютер может находить последовательность P1,P2...Pk очень быстро.

Некая аналогия - ассоциативная памать, когда мы знаем искомое содержимое ячейки памяти, но не знаем адрес этой ячейки. Ассоциативная память мгновенно находит нужную ячейку. Так и тут - мы не знаем последовательность P1,P2...Pk но знаем желаемый результат (число n). Поскольку система квантовая и находиться во всех возможных состояниях одновременно, мы можем найти состояние которое соответствует искомому, и от него определить исходные значания P1,P2...Pk.

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

Другой пример - шахматы или подобная задача с очень большим числом возможных состояний. Вопрос - как ходить. Конечно можно попытаться перебором проанализировать все возможные ответы противника, затем все возможные последующие ходы за нашего игрока, затем опять за противника и т.д. К сожалению очень быстро мы приходим к необходимости анализа чудовищного количества комбинаций, далеко за пределами вычислительных возможностей. А ведь шахматы относительно простая игра - число фигур невелико, и число возможных состояний все-таки можно просчитать. Есть много задач подобного рода но намного сложней.

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

Согласитесь, если действительно удастся построить такую машинку - это будет очень серьезный прогресс, кроме того это может привести к переосмыслению многих фундаментальных идей.
  • +0.00 / 0
  • АУ
 
 
 
 
  Yura_L ( Слушатель )
28 сен 2009 06:10:55


Вот и я о том же. Обещают всякие чудеса, но меня почему-то больше интересует не как все потом будет хорошо благодаря этому, а как оно тикает.
Спрашиваю, какие именно команды выполняют над кубитами, отвечают - другие, квантовые. Спрашиваю, какая там математика - отвечают - другая. Спрашиваю, какие алгоритмы - отвечают - другие. И все. Сплошной туман, и ничего конкретного. Только ругают двоичную систему, а она как раз тут совершенно ни при чем.
Единственно более или менее внятное объяснение встретил у А. Семенова, он объясняет повышение быстродействия за счет бОльшей размерности этих самых кубитов. Типа: обычный байт одномерный, а кубит - к примеру, двумерный. При этом появляются новые возможности. Но говорит об этом только самым абстрактным образом, без примеров конкретной технической реализации.

Но опять же эту структуру можно реализовать на обычной логике, не вижу тут никаких непреодолимых проблем. Однако квантовые компьютерщики говорят - надо непременно на квантовых частицах, иначе никак. Хотя я так понимаю, при использовании оных есть серьезнейшие фундаментальные проблемы, которые напрочь могут похоронить эту идею.
  • +0.00 / 0
  • АУ
 
 
 
 
 
  Midland ( Слушатель )
28 сен 2009 18:31:57


Вы правы, в общем-то любую проблему решаемую квантовым компьютером можно решить классическим компьютером. Просто классический компьютер потратит на решение очень долгое время - квантовый компьютер просто позволяет ускорить перебор. Например вместо десятков лет получить результат за секунду. Согласитесь, это таки может быть полезно.

Посмотрите на устройство классической ассоциативной памяти - по-моему эта аналогия в чем-то похожа.

А если вам интересны детали алгоритмов - кое-что есть на вики: link
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
  Yura_L ( Слушатель )
29 сен 2009 08:44:18


Там опять сплошной туман, какие же операции выполняют кубиты. Говорится только о том, что этот самый кубит находится одновременно во всех возможных состояниях, и якобы именно поэтому иногда (с какой-то вероятностью) выдает правильный результат.

По алгоритмам.
Алгоритм Шора - основан на перемножении по модулю N.   Перемножение по модулю N - самая что ни на есть заурядная операция и на обычной логике выполняется за один такт. Квантовый компьютер для такого алгоритма нужен исключительно для напускания тумана.

Хотя основным назначением алгоритма Гровера принято считать поиск в базе данных, более точно его можно охарактеризовать как «обращение функции». Грубо говоря, имея функцию y=f(x), которая может быть вычислена с использованием квантового компьютера, алгоритм Гровера позволяет вычислить x, зная y. Поиск в базе данных соотносится с обращением функции, которая принимает определенное значение, если аргумент x соответствует искомой записи в базе данных.
Ха. Вот так - взял, и обратил любую функцию. За один такт. Это же самая настоящая волшебная палочка. Поскольку вся математика основана на решении уравнений, а это ни что иное, как обращение функций.

Задача Дойча — Джоза заключается в определении, является ли функция двоичной переменной f(n) постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1).

Для решения этой задачи классическому детерминированному алгоритму необходимо произвести 2n − 1 + 1 вычислений функции f в худшем случае. Классическому вероятностному алгоритму потребуется меньше времени, чтобы дать верный ответ с высокой вероятностью. Но в любом случае для получения верного ответа с единичной вероятностью потребуется 2n − 1 + 1 вычислений. Алгоритм Дойча — Джоза всегда дает верный ответ, совершив лишь одно вычисление значения функции f.

Опять чудеса. Информации, заключающейся в ОДНОМ значении функции f, совершенно недостаточно для предсказания того, как она поведет себя в других точках.
И опять идет описание того, как будет все хорошо и прекрасно, вместо описания принципа действия алгоритма. Опять же, не вижу причин невозможности реализации алгоритма на обычной логике.

Все-таки, какие волшебные действия над кубитами выполняются в квантовом компьютере? И как их описать математически?  Если их нельзя описать математически, то они непригодны для решения практических задач, а если можно - то они легко реализуются на обычном компьютере.

И наконец. Как-то недавно слыхал, что запустили-таки квантовый алгоритм вычисления простых числел, и этот алгоритм уже нашел простое число 2 и простое число 3. Говорят, что в обозримом будущем с помощью этого алгоритма надеются найти простое число 5.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
  Midland ( Слушатель )
29 сен 2009 19:13:12


Юра, а вы почитайте аглицкую версию статей на вики: en.wikipedia.org/wiki/Quantum_algorithm, и пройдитесь по описанию алгоритмов - например Квантового Преобразования Фурье.
Там все вполне детально расписано. Правда много математики. К сожалению русская версия статей никакая, да и многих статей по-русски нет.

Отн "физического смысла" операций с кубитами - это к Добряку. Но что-то мне подсказывает что вообще-то этого никто не понимает. Расчеты делать могут, некие аналогии - есть, а с простым и понятным физическим смыслом - проблема.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
  Senya ( Слушатель )
29 сен 2009 20:21:41
Область лежит слегка позагранью моего понимания, но чуть чуть скажу. С увеличением разрядности время "вычисления" (установления состояния) квантового компьютера растет линейно, а обычного компьютера (например в простом алгоритме поиска решения перебором) - экспоненциально. Недаром в последний раз (точнее последний, пока я еще старался следить) демонстрировалась модель кубайта, состоящая из 256 модулей, работающих впараллель. Модель квантового двойного слова можно попытаться представить (ну лучше не рисковатьУлыбающийся )
ЦитатаИ наконец. Как-то недавно слыхал, что запустили-таки квантовый алгоритм вычисления простых чисел, и этот алгоритм уже нашел простое число 2 и простое число 3. Говорят, что в обозримом будущем с помощью этого алгоритма надеются найти простое число 5.
Не совсем так. Число 6 разложено на простые сомножители 2 и 3, что продемонстрировало возможность реализации математических алгоритмов на реальной системе разрядностью три кубита.
ЗЫ. Лично я относился к квантовым компьютерам с пессимизмом десять лет назад, и сейчас в этом мнении только утвердился.
ЗЗЫ. Вообще простейшая аналогия - решение дифференциальных уравнений на аналоговой вычислительной машине. Ставятся элементы нужных номиналов, замыкается обратная связь, и через некоторое время можно считывать решение. В квантовых компьютерах примерно так же, только аналоговый умножитель с обратной связью не позволит разложить на множители большое число с нужной точностью, а квантовый - может. В сугубой теории.
  • +0.00 / 1
  • АУ
 
 
 
 
 
 
 
 
  Yura_L ( Слушатель )
30 сен 2009 08:22:10


Так я о том же. Если хитрая структура кубита позволяет выполнять не менее хитрые операции и это позволяет ускорить вычисления, то и слава богу. Весь вопрос о том, почему нельзя реализовать этот кубит на обычной логике.
Не нравится бит с двумя состояниями, можно взять 8-битную ячейку с 256-ю состояниями и сопоставить эти состояния с состояниями этого самого кубита. С ними можно выполнять какие угодно операции, и предельно быстро, все это определяется логикой АЛУ. Надо только составить таблицу истинности каждой операции и реализовать их в железе. Единственно, что совершенно непонятно, зачем в кубитах нужно стохастическое состояние, хотя тот же А.Семенов говорит об этом как о недостатке, это следствие редукции волновой функции квантовой частицы. На обычной логике не будет никакой неопределенности, там все детерминировано.
А вот работать с квантовыми частицами - чистая утопия. Как в них записывать информацию и считывать ее? Уровни энергии квантовых частиц, даже в озбужденном состоянии, предельно низкие, а еще есть шумы, от которых никуда не деться. И какое же там будет соотношение сигнал/шум, и связанная с ним вероятность ошибок? Про техническую реализацию подобного устройства вообще лучше не вспоминать.
Что самое интересное, авторы говорят о работе именно с самыми настоящими квантовыми частицами, другие их не устраивают.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
 
 
  Senya ( Слушатель )
30 сен 2009 08:53:56
Можно.
ЦитатаНе нравится бит с двумя состояниями, можно взять 8-битную ячейку с 256-ю состояниями и сопоставить эти состояния с состояниями этого самого кубита. С ними можно выполнять какие угодно операции, и предельно быстро, все это определяется логикой АЛУ. Надо только составить таблицу истинности каждой операции и реализовать их в железе.
Можно. И сделано. Для 2^8=256 состояний. А для вскрытия DES нужно всего-ничего, реализовать в железе таблицу истинности для 2^56=72057594037927936 состояний, но пока не смогли. Для осмысленной задачи по вскрытию самого короткого из реально используемых RSA ключей  - 2^512 состояний.
Цитата А вот работать с квантовыми частицами - чистая утопия. Как в них записывать информацию и считывать ее? Уровни энергии квантовых частиц, даже в озбужденном состоянии, предельно низкие, а еще есть шумы, от которых никуда не деться. И какое же там будет соотношение сигнал/шум, и связанная с ним вероятность ошибок? Про техническую реализацию подобного устройства вообще лучше не вспоминать.
Да. Систему из трех частиц сумели стабилизировать на время, достаточное для получения результата. Для стабилизации системы из 128 частиц (не совсем так - для работы со 128 разрядными числами) встречал оценки - в микроскопическую структуру нужно закачивать порядка 1.5 киловатт. Как отводить эту мощность, чтобы она мгновенно не превратилась в плазму, даже не пытались предполагатьУлыбающийся
ЦитатаЧто самое интересное, авторы говорят о работе именно с самыми настоящими квантовыми частицами, другие их не устраивают.
Время... В обычной системе состояния перебираются по одному (можно конечно выйти на параллелизм в несколько десятков миллионов, но это похоже предел).
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
 
 
 
  Yura_L ( Слушатель )
30 сен 2009 13:11:15


И что, с кубитом можно произвести 2^56 различных операций? А позвольте спросить, какие именно и в какой последовательности?

Если взламывать DES или RSA, то там просто надо произвести кучу параллельных вычислений. А гробится это, например, в DES простым увеличением длины ключа.
И если это все затевается только с целью взлома шифров, то неблагодарное это занятие. Вся теория и практика шифрования заключается в создании алгоритмов, максимально простых для санкционированноно пользователя, и в то же время максимально сложных для взлома.  Ну, допустим, сделали вычислитель, способный взломать DES. А кто мешает на омнове этого же вычислителя создать подобную же систему? Тогда для взлома нужна будет мощность, еще на несколько порядков бОльшая. И всегда шифровальщики будут впереди взломщиков.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
 
 
 
 
  Senya ( Слушатель )
30 сен 2009 13:43:06
Если честно, я не понял. Если нужно, я по порядку могу объяснить, что такое бит, что такое байт, оттуда уже перейдем к кубиту, кубайту и регистрам большей разрядности. А в данной постановке вопрос смысла не имеет.
ЦитатаЕсли взламывать DES или RSA, то там просто надо произвести кучу параллельных вычислений. А гробится это, например, в DES простым увеличением длины ключа.
DES приведен для примера. Для симметричных шифров квантовый компьютер предсказывает лишь уменьшение времени взлома как корень квадратный. (т.е. 128 битный ключ взламывается за время 2^64).
ЦитатаИ если это все затевается только с целью взлома шифров, то неблагодарное это занятие.
Смысл имеет только взлом асимметрики.
ЦитатаНу, допустим, сделали вычислитель, способный взломать DES. А кто мешает на омнове этого же вычислителя создать подобную же систему? Тогда для взлома нужна будет мощность, еще на несколько порядков бОльшая. И всегда шифровальщики будут впереди взломщиков.
Это абсолютно верно для симметричных шифров. Для асимметричных ("с открытым ключом") нет даже близко теоретических проработок. Точнее они появляются регулярно, но пока в них сразу находили грубые ошибки.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
 
 
 
  Yura_L ( Слушатель )
30 сен 2009 13:19:05

Ага. Значит, закачиваем в микроскопическую структуру 1.5 кВт. И эта энергия в микроскопической структуре проявляет себя в виде шума. А полезный сигнал - он ведь тоже энергетический. И какова его энергия? И получается, что полезный сигнал будет на уровне энергии в электрон-вольты, а шумы - в килоджоули.

И еще есть очень большие сомнения в возможности одного кубита выполнять параллельные вычисления. Никто не объяснил, почему и как это происходит.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
 
 
 
 
  Senya ( Слушатель )
30 сен 2009 13:46:55
Какого шума? Испарится нафиг. Никто пока и на 4 кубита не замахнулся.
ЦитатаИ еще есть очень большие сомнения в возможности одного кубита выполнять параллельные вычисления. Никто не объяснил, почему и как это происходит.
Никакие параллельные вычисления он не выполняет и выполнять не может. Равно как и битовая ячейка не может никаких вычислений выполнять. Просто бит находится в одном из двух возможных состояний, а кубит - в суперпозиции этих состояний вплоть до момента считывания с него информации. За теорией, объясняющей квантовые эффекты - я сразу предупредил - не ко мне. Это вне моего понимания. Но в существовании квантовых эффектов сегодня мало кто сомневается.
  • +0.00 / 0
  • АУ
 
 
 
 
 
 
 
 
 
 
 
  Хурон ( Слушатель )
30 сен 2009 17:58:34


Если я что то правильно понял из прочитанного по квантовым вычислениям, то суть их состоит в естественной эволюции связанной ("спутанной") квантовой системы из N кубитов, предустановленной в заданное исходное состояние. И  из этого описания вроде бы неявно следует, что и "код операции" вместе с "данными" тоже как то "предустанавливается" в те же самые кубиты и  влияет на "тип"  квантовой "эволюции".  Ну и, соответственно, на время "вычислений" (от момента "предустановки" до момента "считывания") имеется трудновыполнимое требование "изолированности системы".
  • +0.00 / 0
  • АУ
 
<< Тред №149272
Тред №149274 >>