Сегодня, как я и обещал ранее, я бы хотел поговорить о развитии информатики, точнее не обо всём развитии данной области знаний, а о конкретных предпосылках, приведших к созданию таких направлений как квантовые вычисления и квантовая информация.
Итак, давайте немного уйдем в сторону от «квантов», о которых изначально и шла речь, и обратимся к еще одному интеллектуальному триумфу двадцатого столетия — информатике. Её истоки уходят далеко в глубь веков, подтверждение чему находятся, например, в клинописи древних вавилонян, разработавших некоторые достаточно сложные алгоритмы.
Начало же современной информатики, как многим давно известно, было положено выдающимся математиком Аланом Тьюрингом в его работе 1936 года. Он подробно описал абстрактную модель вычислений, которую мы бы могли назвать программируемым компьютером, которая позже была названа в его честь машиной Тьюринга. Кроме того, нельзя не упомянуть о тезисе Чёрча — Тьюринга, устанавливающего эквивалентность между физическим понятием класса алгоритмов, которые представляется возможным выполнить на некотором физическом устройстве, и строгим математическим понятием универсальной машины Тьюринга. Признание этого тезиса положило начало развитию обширной теории информатики.
Практически сразу же после публикации работы Тьюринга были собраны первые компьютеры на электронных компонентах. Джон фон Нейман разработал простую теоретическую модель, позволяющую объяснить, как на практике собрать компьютер, который будет обладать всеми свойствами универсальной машины Тьюринга. Первый же шаг к настоящей разработке аппаратного обеспечения был сделан в 1947 г., когда был открыт транзистор, после чего мощность «железа» начала расти огромными темпами. И тут следует вспомнить о таком человеке как Гордон Мур, который сформулировал известный всем закон, согласно которому производительность компьютеров, обеспечиваемая при одинаковой цене, должна удваиваться примерно каждые два года.
Как ни странно, но этот закон вполне действует и по сей день, но многие эксперты сходятся во мнении, что уже в ближайшие десятилетия действие закона может прекратиться, в виду появления фундаментальных трудностей, связанных с размерами элементов. Ведь чем меньше становятся электронные устройства, тем больше к их функционированию примешиваются квантовые эффекты.
Одним из возможных решений проблемы как раз и будет переход к другой вычислительной парадигме. Одну из таких парадигм любезно предоставляет нам квантовая теория вычислений. Основана она на использовании квантовой механики, а не классической физики для вычислений. Квантовые компьютеры должны существенно превосходить классические по скорости. Конечно, возможно смоделировать квантовый компьютер с помощью классического, но тут уже встает вопрос об эффективности данной задумки. Так что же мы понимаем под эффективностью? Грубо говоря, под эффективно работающим алгоритма мы подразумеваем алгоритм, время выполнения которого полиномиально зависит от объема решаемой задачи. И тут следует вернуться к области аналоговых вычислений. Некоторые исследователи обнаружили, что определенные типы аналоговых компьютеров могут эффективно решать задачи, не имеющие аналогичного решения на машине Тьюринга. Всё бы ничего, но тут был не учтен один занимательный факт — наличие шума в аналоговых компьютерах, что делало все эти алгоритмы неэффективными. Таким образом, учёт шума в реальных системах стал одним из первых вопросов, которые предстояло решить людям, занимающимся квантовой информатикой и квантовыми вычислениями. А ответом на данный вопрос стала разработка кодов, исправляющих квантовые ошибки, и устойчивых к ошибкам квантовых вычислений.
Первым, кто заинтересовался вопросом квантовых компьютеров стал Дэвид Дойч в 1985 году. Он попытался описать вычислительное устройство, способное моделировать произвольную физическую систему. Так как все законы физики в конечном счете сводятся к квантовомеханическим, то Дойч пришел к рассмотрению вычислительных устройств, основанных на принципах квантовой механики. И именно от этих устройств берет свое начало концепция современного квантового компьютера.
Кроме того, Дойч задался вопросом, который естественным образом появляется в голове: может ли квантовый компьютер эффективно решать задачи, не имеющие аналогичного решения на классических компьютерах? Да, может. Сам Дойч и дал первый ответ на этот вопрос, построив простой пример, показывающий это наглядно.
Этот шаг имел очень большое значение для развития направления, так как в последующие десять лет был существенно развит. Наивысшей точкой данного развития стала демонстрация Питером Шором в 1994 г. того, что исключительно важные задачи, такие как, поиск простых сомножителей целого числа и так называемая задача вычисления дискретного логарифма, могут быть эффективно решены на квантовом компьютере. Вы можете спросить почему же это так важно? Ответ будет чрезвычайно простым: данные задачи до сих пор считаются эффективно неразрешимыми на классических компьютерах.
Еще одно доказательство эффективности показал Лов Гровер в 1995 г., выполнив другую важную задачу — поиск в некотором неструктурированном поисковом пространстве. Надо заметить, что он не дает такого эффективного ускорения как алгоритм Шора, но тем не менее он более эффективен, чем имеющиеся классические аналоги.
Приблизительно в то время начала разрабатываться идея Фейнмана, который высказал мнение, что разработка нового типа компьютеров на основе квантовой механики должно решить проблемы, возникающие с моделирование квантовомеханических систем на «классике». Вероятно, моделирование именно таких систем и станет основным применением квантовых компьютеров.
В заключении хотелось бы немного поговорить о применимости квантовых компьютеров. Основной вопрос тут — имеются ли ещё какие-либо задачи, которые квантовый компьютер может решать быстрее, чем классический? И в ответе на данный вопрос надо быть предельно честным: мы не знаем. Разработка хороших квантовых алгоритмов является достаточно сложной задачей, и на это есть ряд причин. Во-первых, наша интуиция имеет корни в классическом представлении мира, а, соответственно, придуманные нами идеи скорее всего будут классическими. Чтобы уйти от этого нам нужно попытаться отключить классическую интуицию и хоть ненадолго отдаться в руки квантовых эффектов и квантовой логики. Во-вторых, мало придумать работающий алгоритм, необходимо также, чтобы он был лучше уже имеющихся классических! Решение этих проблем-основное направление развития новых квантовых алгоритмов для будущего. Можно поставить вопрос по-другому: что именно квантовые компьютеры делают эффективнее, чем классические, если это конечно на самом деле так? И опять мы возвращаемся к тому, насколько мало мы знаем о квантовых вычислениях и квантовой информации. Необходимость лучшего понимания данных вещей и есть тот самый главный вызов на пути к появлению квантового компьютера.
Спасибо за внимание!
Информатика.
Итак, давайте немного уйдем в сторону от «квантов», о которых изначально и шла речь, и обратимся к еще одному интеллектуальному триумфу двадцатого столетия — информатике. Её истоки уходят далеко в глубь веков, подтверждение чему находятся, например, в клинописи древних вавилонян, разработавших некоторые достаточно сложные алгоритмы.
Начало же современной информатики, как многим давно известно, было положено выдающимся математиком Аланом Тьюрингом в его работе 1936 года. Он подробно описал абстрактную модель вычислений, которую мы бы могли назвать программируемым компьютером, которая позже была названа в его честь машиной Тьюринга. Кроме того, нельзя не упомянуть о тезисе Чёрча — Тьюринга, устанавливающего эквивалентность между физическим понятием класса алгоритмов, которые представляется возможным выполнить на некотором физическом устройстве, и строгим математическим понятием универсальной машины Тьюринга. Признание этого тезиса положило начало развитию обширной теории информатики.
Практически сразу же после публикации работы Тьюринга были собраны первые компьютеры на электронных компонентах. Джон фон Нейман разработал простую теоретическую модель, позволяющую объяснить, как на практике собрать компьютер, который будет обладать всеми свойствами универсальной машины Тьюринга. Первый же шаг к настоящей разработке аппаратного обеспечения был сделан в 1947 г., когда был открыт транзистор, после чего мощность «железа» начала расти огромными темпами. И тут следует вспомнить о таком человеке как Гордон Мур, который сформулировал известный всем закон, согласно которому производительность компьютеров, обеспечиваемая при одинаковой цене, должна удваиваться примерно каждые два года.
Эффективность алгоритмов.
Как ни странно, но этот закон вполне действует и по сей день, но многие эксперты сходятся во мнении, что уже в ближайшие десятилетия действие закона может прекратиться, в виду появления фундаментальных трудностей, связанных с размерами элементов. Ведь чем меньше становятся электронные устройства, тем больше к их функционированию примешиваются квантовые эффекты.
Одним из возможных решений проблемы как раз и будет переход к другой вычислительной парадигме. Одну из таких парадигм любезно предоставляет нам квантовая теория вычислений. Основана она на использовании квантовой механики, а не классической физики для вычислений. Квантовые компьютеры должны существенно превосходить классические по скорости. Конечно, возможно смоделировать квантовый компьютер с помощью классического, но тут уже встает вопрос об эффективности данной задумки. Так что же мы понимаем под эффективностью? Грубо говоря, под эффективно работающим алгоритма мы подразумеваем алгоритм, время выполнения которого полиномиально зависит от объема решаемой задачи. И тут следует вернуться к области аналоговых вычислений. Некоторые исследователи обнаружили, что определенные типы аналоговых компьютеров могут эффективно решать задачи, не имеющие аналогичного решения на машине Тьюринга. Всё бы ничего, но тут был не учтен один занимательный факт — наличие шума в аналоговых компьютерах, что делало все эти алгоритмы неэффективными. Таким образом, учёт шума в реальных системах стал одним из первых вопросов, которые предстояло решить людям, занимающимся квантовой информатикой и квантовыми вычислениями. А ответом на данный вопрос стала разработка кодов, исправляющих квантовые ошибки, и устойчивых к ошибкам квантовых вычислений.
Квантовый компьютер.
Первым, кто заинтересовался вопросом квантовых компьютеров стал Дэвид Дойч в 1985 году. Он попытался описать вычислительное устройство, способное моделировать произвольную физическую систему. Так как все законы физики в конечном счете сводятся к квантовомеханическим, то Дойч пришел к рассмотрению вычислительных устройств, основанных на принципах квантовой механики. И именно от этих устройств берет свое начало концепция современного квантового компьютера.
Кроме того, Дойч задался вопросом, который естественным образом появляется в голове: может ли квантовый компьютер эффективно решать задачи, не имеющие аналогичного решения на классических компьютерах? Да, может. Сам Дойч и дал первый ответ на этот вопрос, построив простой пример, показывающий это наглядно.
Этот шаг имел очень большое значение для развития направления, так как в последующие десять лет был существенно развит. Наивысшей точкой данного развития стала демонстрация Питером Шором в 1994 г. того, что исключительно важные задачи, такие как, поиск простых сомножителей целого числа и так называемая задача вычисления дискретного логарифма, могут быть эффективно решены на квантовом компьютере. Вы можете спросить почему же это так важно? Ответ будет чрезвычайно простым: данные задачи до сих пор считаются эффективно неразрешимыми на классических компьютерах.
Еще одно доказательство эффективности показал Лов Гровер в 1995 г., выполнив другую важную задачу — поиск в некотором неструктурированном поисковом пространстве. Надо заметить, что он не дает такого эффективного ускорения как алгоритм Шора, но тем не менее он более эффективен, чем имеющиеся классические аналоги.
Приблизительно в то время начала разрабатываться идея Фейнмана, который высказал мнение, что разработка нового типа компьютеров на основе квантовой механики должно решить проблемы, возникающие с моделирование квантовомеханических систем на «классике». Вероятно, моделирование именно таких систем и станет основным применением квантовых компьютеров.
Заключение.
В заключении хотелось бы немного поговорить о применимости квантовых компьютеров. Основной вопрос тут — имеются ли ещё какие-либо задачи, которые квантовый компьютер может решать быстрее, чем классический? И в ответе на данный вопрос надо быть предельно честным: мы не знаем. Разработка хороших квантовых алгоритмов является достаточно сложной задачей, и на это есть ряд причин. Во-первых, наша интуиция имеет корни в классическом представлении мира, а, соответственно, придуманные нами идеи скорее всего будут классическими. Чтобы уйти от этого нам нужно попытаться отключить классическую интуицию и хоть ненадолго отдаться в руки квантовых эффектов и квантовой логики. Во-вторых, мало придумать работающий алгоритм, необходимо также, чтобы он был лучше уже имеющихся классических! Решение этих проблем-основное направление развития новых квантовых алгоритмов для будущего. Можно поставить вопрос по-другому: что именно квантовые компьютеры делают эффективнее, чем классические, если это конечно на самом деле так? И опять мы возвращаемся к тому, насколько мало мы знаем о квантовых вычислениях и квантовой информации. Необходимость лучшего понимания данных вещей и есть тот самый главный вызов на пути к появлению квантового компьютера.
Спасибо за внимание!
Комментарии (7)
dtestyk
21.10.2015 18:35-1По поводу эффективности квантовых компьютеров:
давно уже интересует вопрос о преимуществах квантовых компьютеров перед оптическими: полупрозрачные зеркала дадут квантовый эффект распараллеливания.
Кроме того, так как фотоны не взаимодействуют между собой можно выполнять сколько угодно параллельных вычислений.
З.Ы. Последнее утверждение не претендует на истинность, но все равно можно совмещать вычисления на нескольких частотах в одном объеме.
dtestyk
21.10.2015 20:37И еще интересно: если квантовые процессы обратимы, то вычисления в прямом и обратном порядке должны занимать одинаковое время. Т.е. если при вычислении хеш функции не будет происходить потери информации, то можно вычислить обратную ей за такое же время. Так ли это?
DmitriyN
21.10.2015 23:44В большинстве квантовых алгоритмов участвуют вспомогательные кубиты (ancilla qubit). В прямом вычислении их значение не важно и их выбрасывают. Но для того, чтобы обратить алгоритм, их надо откуда-то взять. Так что ответ на ваш вопрос — нет.
Eol
23.10.2015 01:17+1Если при вычислении хэш функции не происходит потери информации, то это уже не хэш функция вовсе, а в лучшем случае архиватор.
qbertych
Квантовые вычисления без Фейнмана — это примерно как кинематограф без Чаплина. Вы бы хотя бы википедию открыли.
Хотелось бы поподробнее, где можно почитать?
kronos_god
1) как я и сказал вначале, я говорю о этапах, имевших влияние на квантовые вычисления. Не слышал, о влиянии квантовых эффектов на ламповые.
2) не спорю про вклад Феймана, но я говорю конкретно про предшественников квантовых компьютеров.
3) это идеальные теоретические модели, знаю, что это было, но конкретных ссылок дать не могу