Сергей Ширкин - Задача Дойча (подробное объяснение)

Пожалуй, один из самых подробных и понятных разборов задачи Дойча. Обязательно к просмотру, если вам не удалось понять этот популярный алгоритм квантовых вычислений по другим источникам. После просмотра данного видео все вопросы должны проясниться. Задача Дойча (Deutsch's algorithm) - первый алгоритм, показавший превосходство кванового компьютера по сравнению с классическими компьютерами. Задача алгоритма - определить, какая функция находится в черном ящике - константная или сбалансированная. На вход функции подаются числа из множества {0, 1} и на выходе также получаются числа из этого множества. Если для классического компьютера такая задача решается в два шага (нужно проверить функцию для входного значения 0, а затем для 1), то для квантового компьютера достаточно одного запуска функции.