Иску́сственный интелле́кт в самом широком смысле – это интеллект, демонстрируемый машинами, в частности компьютерными системами. Это область исследований в области компьютерных наук, которая разрабатывает и изучает методы и программное обеспечение, позволяющие машинам воспринимать окружающую среду и использовать обучение и интеллект для выполнения действий, которые максимально увеличивают их шансы на достижение поставленных целей. Такие машины можно назвать искусственным интеллектом.
Куби́т — наименьшая единица информации в квантовом компьютере, использующаяся для квантовых вычислений.
Ква́нтовый компью́тер — вычислительное устройство, которое использует явления квантовой механики для передачи и обработки данных. Квантовый компьютер оперирует не битами, а кубитами, имеющими значения одновременно и 0, и 1. Теоретически это позволяет обрабатывать все возможные состояния одновременно, достигая существенного преимущества над обычными компьютерами в ряде алгоритмов.
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах, а под размером выхода — длина описания решения задачи.
Машинное обучение — класс методов искусственного интеллекта, характерной чертой которых является не прямое решение задачи, а обучение за счёт применения решений множества сходных задач. Для построения таких методов используются средства математической статистики, численных методов, математического анализа, методов оптимизации, теории вероятностей, теории графов, различные техники работы с данными в цифровой форме.
Data mining — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году.
Метод случайного леса — алгоритм машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана и метод случайных подпространств, предложенный Тин Кам Хо. Алгоритм применяется для задач классификации, регрессии и кластеризации. Основная идея заключается в использовании большого ансамбля решающих деревьев, каждое из которых само по себе даёт очень невысокое качество классификации, но за счёт их большого количества результат получается хорошим.
Обуче́ние ранжи́рованию — это класс задач машинного обучения с учителем, заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных частичных порядков на элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента. Цель ранжирующей модели — наилучшим образом приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.
Питер Шор — американский учёный. Автор работ в области геометрии, теории вероятностей, комбинаторики, теории алгоритмов и квантовой информатики. Наиболее известен своими основополагающими результатами в теории квантовых вычислений.
Квантовая информатика — раздел науки, возникший в конце XX века на стыке квантовой механики, теории алгоритмов и теории информации. В квантовой информатике изучаются общие принципы и законы, управляющие динамикой сложных квантовых систем. Моделью таких систем является квантовый компьютер.
Идея квантовых вычислений была независимо предложена Юрием Маниным и Ричардом Фейнманом в начале 1980-х. С тех пор была проделана колоссальная работа для построения работающего квантового компьютера.
Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми для криптографических атак. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора. Многие криптографы в настоящее время ведут разработку алгоритмов, независимых от квантовых вычислений, то есть устойчивых к квантовым атакам.
В криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом, который они используют для шифрования сообщений между собой. RLWE-KEX является одним из алгоритмов с открытым ключом, который предназначен для защиты от противника, обладающего квантовым компьютером. Это важно, потому что криптографические системы с открытым ключом, широко используемые сегодня, легко взламываются квантовым компьютером. RLWE-KEX является одним из множества постквантовых криптографических алгоритмов, основанных на сложности решения математических задач, связанных с криптографией на решётках.
Индукция грамматики — процедура машинного обучения, которая восстанавливает формальную грамматику языка на основе набора наблюдений (примеров) с известной принадлежностью этому языку. В результате процедуры строится модель наблюдаемых объектов в виде набора правил вывода или порождающих правил, конечного автомата или автомата другого вида. В более общем смысле, грамматический вывод — это одно из направлений машинного обучения, в котором пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья, графы.
Ансамблевое обучение — техника машинного обучения, использующая несколько обученных алгоритмов с целью получения лучшей предсказательной эффективности, чем можно было бы получить от каждого алгоритма по отдельности. В отличие от статистического ансамбля в статистической механике, который обычно бесконечен, ансамбль моделей в машинном обучении состоит из конкретного конечного множества альтернативных моделей, но обычно позволяет существовать гораздо более гибким структурам.
Вероятно приближённо корректное обучение — схема машинного обучения, использующая понятия асимптотической достоверности и вычислительной сложности. Предложена в 1984 году Лесли Вэлиантом.
Теория вычислительного обучения — это подобласть теории искусственного интеллекта, посвящённая разработке и анализу алгоритмов машинного обучения.
Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а также проблемы, связанные с этими классами сложности, и связи между классами квантовой сложности и классическими (неквантовыми) классами сложности.
Подпись при обучении с ошибками в кольце — один из классов криптосистем с открытым ключом, основанный на задаче обучения с ошибками в кольце, который заменяет используемые алгоритмы подписи RSA и ECDSA. В течение последнего десятилетия проводились активные исследования по созданию криптографических алгоритмов, которые остаются безопасными, даже если у злоумышленника есть ресурсы квантового компьютера. Подпись при обучении с ошибками в кольце относится к числу пост-квантовых подписей с наименьшим открытым ключом и размерами подписи. Использование общей проблемы обучения с ошибками в криптографии было введено Одедом Регевым в 2005 году и послужило источником нескольких криптографических разработок. Основоположники криптографии при обучении с ошибками в кольце, считают, что особенностью этих алгоритмов, основанных на обучении с ошибками, является доказуемое сокращение известных сложных задач. Данная подпись имеет доказуемое сокращение до задачи нахождения кратчайшего вектора в области криптографии на решётках. Это означает, что если можно обнаружить атаку на криптосистему RLWE, то целый класс предполагаемых сложных вычислительных проблем будет иметь решение. Первая подпись на основе RLWE была разработана Вадимом Любашевским и уточнена в 2011 году. Данная статья освещает фундаментальные математические основы RLWE и основана на схеме под названием GLYPH.
Одед Регев — израильско-американский учёный, теоретик информатики и математик. Лауреат премии Гёделя. Профессор информатики в Курантовском институте при Нью-Йоркском университете. Наиболее известен своими работами в области решётчатой криптографии, в частности постановкой задачи обучения с ошибками (LWE), криптоанализом схем GGH и NTRUSign, а также разработкой нового квантового алгоритма по факторизации чисел, превосходящего по эффективности алгоритм Шора.