Comments 3
Странные задачи, странные проблемы, странные решения
Пушка для стрельбы по воробьям.
Так же и в ответ на статью: kruegger 19 декабря 2019 в 13:18 в habr.com/ru/post/480480 «Как работают квантовые компьютеры. Собираем паззл»
Выдержка из статьи:
Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).
Как решать эту задачу?
Решение
Решаем задачу на простейшем аналоговом компьютере.
1. Схема компьютера
(К сожалению предложенный редактор не совершенен и не позволяет прямо вводить картинки и формулы. Почему то нет возможности просто посылать файлы. Странный Хабр. Если интересно, то могу прислать файл из под нормального редактора по почте. Мой адрес: oleg-maevsky@yandex.ru)
Компьютер состоит из измерителя сопротивления, из N коробочек с резистором сопротивлением от 1 килоома до N килоом и выключателем, состояние выключателя зависит от наличия мячика в коробочке. Состояние коробочки без мячика — открытый контакт. Состояние коробочки с мячиком — замкнутый контакт. Абсолютно очевидно, что измеритель сопротивления сразу, за один шаг измерений покажет номер коробочки, который совпадет с количеством килоом на панели прибора. Решение просто и смешно до идиотизма! В чем же здесь дело?
Дело в глобальном непонимании сути алгоритмической проблемы, в самой ее формулировке. Вернемся к сформулированной в самом начале задаче:
"… имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик ..."
Выше мы решили эту задачу в полном соответствии с данным условием. Однако, испытываем некий дискомфорт, не так ли? В чем же дело? Дело в том, что проблема не в самом поиске мячика, а в вопросе как подготовить исходные данные? Как их загрузить в компьютер? И не важно какой это компьютер квантовый или деревянный. Прежде, чем загружать данные необходимо создать хранилище этих данных. Или как говорят программисты выделить память. Не кажется ли вам, что это уже требует времени? Сколько времени? Затем, исходные данные надо загрузить. Как? Сколько для этого надо совершить шагов. В традиционном компьютере понадобится N шагов (вместе с выделением памяти). А сколько шагов надо потратить для ввода исходных данных в квантовом компьютере для этой задачи? Не уж то менее, чем N? Если да, то поделитесь пожалуйста как это так получится. Может быть еще и N мячиков удастся разместить в N-1 коробочке?
А, вот в последней фразе как раз и кроется смысл абсурда. Если поразмыслить над абсурдностью фразы, то через пару мгновений на ум приходит озарение — проблема неэффективности решения многих алгоритмических задач теряется в самой ее формулировке.
Рассмотрим теперь задачу "… нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных ...". В литературе постоянно твердят о том, что эта задача NP полная. Но это не совсем так. Чтобы не обижать многих авторов, предлагаю более мягкую формулировку заявления: эта задача имеет экспоненциальную сложность, если в ее формулировку входит и проблема размещения и проблема ввода данных в компьютере одновременно с проблемой поиска решений. Доказано (см. оценки сложности представления булевых функций где-нибудь в википедии), что в общем случае сложность представления булевой функции (любым способом) оценивается как О(), где n — число входных переменных. Поэтому, грубо говоря, чтобы просто ввести входные данные для любого алгоритма решения уравнения F(X) = 1, где X — n компонентный вектор входных переменных, уже потребуется как минимум шагов. А далее все просто. Существует, например, структура данных для хранения булевых функций, которая называется RoBDD (Reduced Binary Decision Diagrams), сложность которой порядка, сложность загрузки та же, а сложность логических операций в них порядка n, причем, это не только операции поиска решения уравнения F(X) = 1, но и любые логические операции между двумя логическими функциями, а так же операции подсчета числа единичных значений функции и многих других операций, которые уже по своей природе не называются логическими. А, как, интересно, любители квантовых вычислений предлагают загружать входные данные для решения уравнения F(X) = 1?
Вывод: прежде, чем ломать копья о ветряные мельницы или тащить пушку для стребы по воробьям подумайте лишний раз над формулировкой той задачи, на которую замахнулись.
Пушка для стрельбы по воробьям.
Так же и в ответ на статью: kruegger 19 декабря 2019 в 13:18 в habr.com/ru/post/480480 «Как работают квантовые компьютеры. Собираем паззл»
Выдержка из статьи:
Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).
Как решать эту задачу?
Решение
Решаем задачу на простейшем аналоговом компьютере.
1. Схема компьютера
(К сожалению предложенный редактор не совершенен и не позволяет прямо вводить картинки и формулы. Почему то нет возможности просто посылать файлы. Странный Хабр. Если интересно, то могу прислать файл из под нормального редактора по почте. Мой адрес: oleg-maevsky@yandex.ru)
Компьютер состоит из измерителя сопротивления, из N коробочек с резистором сопротивлением от 1 килоома до N килоом и выключателем, состояние выключателя зависит от наличия мячика в коробочке. Состояние коробочки без мячика — открытый контакт. Состояние коробочки с мячиком — замкнутый контакт. Абсолютно очевидно, что измеритель сопротивления сразу, за один шаг измерений покажет номер коробочки, который совпадет с количеством килоом на панели прибора. Решение просто и смешно до идиотизма! В чем же здесь дело?
Дело в глобальном непонимании сути алгоритмической проблемы, в самой ее формулировке. Вернемся к сформулированной в самом начале задаче:
"… имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик ..."
Выше мы решили эту задачу в полном соответствии с данным условием. Однако, испытываем некий дискомфорт, не так ли? В чем же дело? Дело в том, что проблема не в самом поиске мячика, а в вопросе как подготовить исходные данные? Как их загрузить в компьютер? И не важно какой это компьютер квантовый или деревянный. Прежде, чем загружать данные необходимо создать хранилище этих данных. Или как говорят программисты выделить память. Не кажется ли вам, что это уже требует времени? Сколько времени? Затем, исходные данные надо загрузить. Как? Сколько для этого надо совершить шагов. В традиционном компьютере понадобится N шагов (вместе с выделением памяти). А сколько шагов надо потратить для ввода исходных данных в квантовом компьютере для этой задачи? Не уж то менее, чем N? Если да, то поделитесь пожалуйста как это так получится. Может быть еще и N мячиков удастся разместить в N-1 коробочке?
А, вот в последней фразе как раз и кроется смысл абсурда. Если поразмыслить над абсурдностью фразы, то через пару мгновений на ум приходит озарение — проблема неэффективности решения многих алгоритмических задач теряется в самой ее формулировке.
Рассмотрим теперь задачу "… нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных ...". В литературе постоянно твердят о том, что эта задача NP полная. Но это не совсем так. Чтобы не обижать многих авторов, предлагаю более мягкую формулировку заявления: эта задача имеет экспоненциальную сложность, если в ее формулировку входит и проблема размещения и проблема ввода данных в компьютере одновременно с проблемой поиска решений. Доказано (см. оценки сложности представления булевых функций где-нибудь в википедии), что в общем случае сложность представления булевой функции (любым способом) оценивается как О(), где n — число входных переменных. Поэтому, грубо говоря, чтобы просто ввести входные данные для любого алгоритма решения уравнения F(X) = 1, где X — n компонентный вектор входных переменных, уже потребуется как минимум шагов. А далее все просто. Существует, например, структура данных для хранения булевых функций, которая называется RoBDD (Reduced Binary Decision Diagrams), сложность которой порядка, сложность загрузки та же, а сложность логических операций в них порядка n, причем, это не только операции поиска решения уравнения F(X) = 1, но и любые логические операции между двумя логическими функциями, а так же операции подсчета числа единичных значений функции и многих других операций, которые уже по своей природе не называются логическими. А, как, интересно, любители квантовых вычислений предлагают загружать входные данные для решения уравнения F(X) = 1?
Вывод: прежде, чем ломать копья о ветряные мельницы или тащить пушку для стребы по воробьям подумайте лишний раз над формулировкой той задачи, на которую замахнулись.
Странные задачи, странные проблемы, странные решения
Пушка для стрельбы по воробьям.
Так же и в ответ на статью: kruegger 19 декабря 2019 в 13:18 в habr.com/ru/post/480480 «Как работают квантовые компьютеры. Собираем паззл»
Выдержка из статьи:
Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).
Как решать эту задачу?
Решение
Решаем задачу на простейшем аналоговом компьютере.
1. Схема компьютера
(К сожалению предложенный редактор не совершенен и не позволяет прямо вводить картинки и формулы. Почему то нет возможности просто посылать файлы. Странный Хабр. Если интересно, то могу прислать файл из под нормального редактора по почте. Мой адрес: oleg-maevsky@yandex.ru)
Компьютер состоит из измерителя сопротивления, из N коробочек с резистором сопротивлением от 1 килоома до N килоом и выключателем, состояние выключателя зависит от наличия мячика в коробочке. Состояние коробочки без мячика — открытый контакт. Состояние коробочки с мячиком — замкнутый контакт. Абсолютно очевидно, что измеритель сопротивления сразу, за один шаг измерений покажет номер коробочки, который совпадет с количеством килоом на панели прибора. Решение просто и смешно до идиотизма! В чем же здесь дело?
Дело в глобальном непонимании сути алгоритмической проблемы, в самой ее формулировке. Вернемся к сформулированной в самом начале задаче:
"… имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик ..."
Выше мы решили эту задачу в полном соответствии с данным условием. Однако, испытываем некий дискомфорт, не так ли? В чем же дело? Дело в том, что проблема не в самом поиске мячика, а в вопросе как подготовить исходные данные? Как их загрузить в компьютер? И не важно какой это компьютер квантовый или деревянный. Прежде, чем загружать данные необходимо создать хранилище этих данных. Или как говорят программисты выделить память. Не кажется ли вам, что это уже требует времени? Сколько времени? Затем, исходные данные надо загрузить. Как? Сколько для этого надо совершить шагов. В традиционном компьютере понадобится N шагов (вместе с выделением памяти). А сколько шагов надо потратить для ввода исходных данных в квантовом компьютере для этой задачи? Не уж то менее, чем N? Если да, то поделитесь пожалуйста как это так получится. Может быть еще и N мячиков удастся разместить в N-1 коробочке?
А, вот в последней фразе как раз и кроется смысл абсурда. Если поразмыслить над абсурдностью фразы, то через пару мгновений на ум приходит озарение — проблема неэффективности решения многих алгоритмических задач теряется в самой ее формулировке.
Рассмотрим теперь задачу "… нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных ...". В литературе постоянно твердят о том, что эта задача NP полная. Но это не совсем так. Чтобы не обижать многих авторов, предлагаю более мягкую формулировку заявления: эта задача имеет экспоненциальную сложность, если в ее формулировку входит и проблема размещения и проблема ввода данных в компьютере одновременно с проблемой поиска решений. Доказано (см. оценки сложности представления булевых функций где-нибудь в википедии), что в общем случае сложность представления булевой функции (любым способом) оценивается как О(2^n-1), где n — число входных переменных. Поэтому, грубо говоря, чтобы просто ввести входные данные для любого алгоритма решения уравнения F(X) = 1, где X — n компонентный вектор входных переменных, уже потребуется как минимум 2^n-1 шагов. А далее все просто. Существует, например, структура данных для хранения булевых функций, которая называется RoBDD (Reduced Binary Decision Diagrams), сложность которой порядка2^n-1, сложность загрузки та же, а сложность логических операций в них порядка n, причем, это не только операции поиска решения уравнения F(X) = 1, но и любые логические операции между двумя логическими функциями, а так же операции подсчета числа единичных значений функции и многих других операций, которые уже по своей природе не называются логическими. А, как, интересно, любители квантовых вычислений предлагают загружать входные данные для решения уравнения F(X) = 1?
Вывод: прежде, чем ломать копья о ветряные мельницы или тащить пушку для стребы по воробьям подумайте лишний раз над формулировкой той задачи, на которую замахнулись.
Пушка для стрельбы по воробьям.
Так же и в ответ на статью: kruegger 19 декабря 2019 в 13:18 в habr.com/ru/post/480480 «Как работают квантовые компьютеры. Собираем паззл»
Выдержка из статьи:
Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).
Как решать эту задачу?
Решение
Решаем задачу на простейшем аналоговом компьютере.
1. Схема компьютера
(К сожалению предложенный редактор не совершенен и не позволяет прямо вводить картинки и формулы. Почему то нет возможности просто посылать файлы. Странный Хабр. Если интересно, то могу прислать файл из под нормального редактора по почте. Мой адрес: oleg-maevsky@yandex.ru)
Компьютер состоит из измерителя сопротивления, из N коробочек с резистором сопротивлением от 1 килоома до N килоом и выключателем, состояние выключателя зависит от наличия мячика в коробочке. Состояние коробочки без мячика — открытый контакт. Состояние коробочки с мячиком — замкнутый контакт. Абсолютно очевидно, что измеритель сопротивления сразу, за один шаг измерений покажет номер коробочки, который совпадет с количеством килоом на панели прибора. Решение просто и смешно до идиотизма! В чем же здесь дело?
Дело в глобальном непонимании сути алгоритмической проблемы, в самой ее формулировке. Вернемся к сформулированной в самом начале задаче:
"… имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик ..."
Выше мы решили эту задачу в полном соответствии с данным условием. Однако, испытываем некий дискомфорт, не так ли? В чем же дело? Дело в том, что проблема не в самом поиске мячика, а в вопросе как подготовить исходные данные? Как их загрузить в компьютер? И не важно какой это компьютер квантовый или деревянный. Прежде, чем загружать данные необходимо создать хранилище этих данных. Или как говорят программисты выделить память. Не кажется ли вам, что это уже требует времени? Сколько времени? Затем, исходные данные надо загрузить. Как? Сколько для этого надо совершить шагов. В традиционном компьютере понадобится N шагов (вместе с выделением памяти). А сколько шагов надо потратить для ввода исходных данных в квантовом компьютере для этой задачи? Не уж то менее, чем N? Если да, то поделитесь пожалуйста как это так получится. Может быть еще и N мячиков удастся разместить в N-1 коробочке?
А, вот в последней фразе как раз и кроется смысл абсурда. Если поразмыслить над абсурдностью фразы, то через пару мгновений на ум приходит озарение — проблема неэффективности решения многих алгоритмических задач теряется в самой ее формулировке.
Рассмотрим теперь задачу "… нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных ...". В литературе постоянно твердят о том, что эта задача NP полная. Но это не совсем так. Чтобы не обижать многих авторов, предлагаю более мягкую формулировку заявления: эта задача имеет экспоненциальную сложность, если в ее формулировку входит и проблема размещения и проблема ввода данных в компьютере одновременно с проблемой поиска решений. Доказано (см. оценки сложности представления булевых функций где-нибудь в википедии), что в общем случае сложность представления булевой функции (любым способом) оценивается как О(2^n-1), где n — число входных переменных. Поэтому, грубо говоря, чтобы просто ввести входные данные для любого алгоритма решения уравнения F(X) = 1, где X — n компонентный вектор входных переменных, уже потребуется как минимум 2^n-1 шагов. А далее все просто. Существует, например, структура данных для хранения булевых функций, которая называется RoBDD (Reduced Binary Decision Diagrams), сложность которой порядка2^n-1, сложность загрузки та же, а сложность логических операций в них порядка n, причем, это не только операции поиска решения уравнения F(X) = 1, но и любые логические операции между двумя логическими функциями, а так же операции подсчета числа единичных значений функции и многих других операций, которые уже по своей природе не называются логическими. А, как, интересно, любители квантовых вычислений предлагают загружать входные данные для решения уравнения F(X) = 1?
Вывод: прежде, чем ломать копья о ветряные мельницы или тащить пушку для стребы по воробьям подумайте лишний раз над формулировкой той задачи, на которую замахнулись.
Sign up to leave a comment.
Как разобраться с пауками в квантовой программе