Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Известия Российской академии наук Серия математическая

О квантовой коммуникационной сложности симметрических предикатов

Александр Александрович Разборов, Alexander Alexandrovich Razborov

Published Jan 1, 2003• 6 citations
Publisher

Abstract

А. А. Разборов О квантовой коммуникационной сложности симметрических предикатов С точностью до логарифмического множителя определяется коммуникацион ная сложность вычисления произвольной, зависящей лишь от \х П г/|, функции /(ж, г/), х,у С [п], с допустимой вероятностью ошибки, отделенной от 1/2.Бо лее точно, для предиката D на множестве {0,1,..., п} полагаемПолученный результат выполняется как в модели с предварительным зацеплением, так и в модели без такого зацепления.Библиография: 26 наименований.§ 1. Введение С момента, когда модель коммуникационной сложности была впервые рассмот рена в работе [25], она развилась в важное самостоятельное направление теории вычислительной сложности, позволяющее, в частности, взглянуть с единой точки зрения на целый ряд разнородных понятий.В этой модели участвуют два игро ка, по традиции называемые Алиса и Боб.У Алисы имеется некоторый элемент х из фиксированного конечного множества X, у Боба -другой элемент у £ F, и их задача состоит в вычислении некоторого (данного заранее) булевого предиката f: X xY ^ {0,1} путем обмена сообщениями.Сложность измеряется суммарной битовой длиной пересланных сообщений, и так же, как и во многих других разде лах теории вычислительной сложности, при этом различают детерминированные и вероятностные алгоритмы.Точно так же, как в теории сложности булевых схем часто рассматривают симметрические булевы функции, значительный интерес в теории коммуникаци онной сложности представляют симметрические предикаты, определяемые как такие /, для которых хну -конечные множества и значение / задается формулой Работа выполнена во время командировки в Институт перспективных исследований (Принстон, США), поддержанной Фондом им.фон Неймана.

DOI
10.4213/im422

Related papers

О квантовотеоретическом истолковании кинематических и механических соотношений

Werner Karl Heisenberg

в. ГЕЙЗЕНБЕРГ что они напоминают те парадоксы, которые появились при анализе явлений излучения.Отказ от пространственно-временных образов характерен для формального рассмотрения проблем теории излучения и механической теории теплоты.Подобное рассмотрение было предпринято в недавно появившихся работах де Бройля *) и Эйнштейна **).С точки зрения' перспективы, которую открывают эти работы, я считал бы, что содержащиеся в настоящей работе соображения могут иметь некоторый интерес.Поэтому я решил опубликовать эту работу без изменений, хотя лежащие в ее основе стремления теперь могут показаться, пожалуй, безнадежными.530.145.6 О КВАНТОВОТЕОРЕТИЧЕСКОМ ИСТОЛКОВАНИИ КИНЕМАТИЧЕСКИХ И МЕХАНИЧЕСКИХ СООТНОШЕНИЙ***) В. Гейзенберг (Гёттинген) (Поступило 29 июля 1925 г.) В этой работе делается попытка получить основы квантовотеоретической механики, которые базируются исключительно на соотношениях между принципиально наблюдаемыми величинами.Как широко известно, против формальных правил, которые используются в квантовой теории для вычисления наблюдаемых величин (например, энергии водородного атома), выдвигаются серьезные возражения: эти правила содержат в качестве существенной составной части отношения между величинами, которые, по-видимому, принципиально не могут быть наблюдаемы (каковы, например, положение и время обращения электрона).Таким образом, этим правилам явно недостает какого-либо наглядного физического фундамента, если все еще не придерживаться надежды, что такие до сих пор ненаблюдаемые величины, возможно, могут стать доступными эксперименту когда-либо позднее.Такая надежда могла бы считаться правомерной, если бы упомянутые правила были сами по себе последовательны и применимы в какой-либо определенной ограниченной области квантовотеоретических проблем.Но опыт показывает, что эти формальные правила квантовой теории пригодны только для задач об атоме водорода и его эффекте Штарка, но уже в задаче о «скрещенных полях» («gekreuzten Felder») (атом водорода в электрическом и магнитном полях различного направления) появляются фундаментальные трудности, состоящие в том, что взаимодействие атома с периодически меняющимися полями, несомненно, не может удовлетворительно описываться с помощью названных правил и, что, наконец, распространение этих правил на описание атомов со многими электронами оказалось невозможным.Стало обычным считать эти неудачи квантовотеоретических правил, которые ведь по-существу, характеризовались применением классической механики, как отклонение от классической механики.Но

Uspekhi Fizicheskih Nauk•Jan 1, 1977•2 citations

Когерентные состояния для групп движений симметрических пространств

М.И. Монастырский, А.М. Переломов

МАТЕМАТИЧЕСКАЯ ФИЗИКА М. И. МОНАСТЫРСКИЙ, А. М. ПЕРЕЛОМОВ КОГЕРЕНТНЫЕ СОСТОЯНИЯ ДЛЯ ГРУПП ДВИЖЕНИЙ СИММЕТРИЧЕСКИХ ПРОСТРАНСТВ (Представлено академиком Я. Б. Зельдовичем 22 II 1974) В настоящей работе мы продолжим начатое в (*) исследование обоб щенных когерентных состояний (о.к.с.), не являющихся квадратично-интегрируемыми.О.к.с., введенные в (2), так же как и обычные когерент ные состояния (3), оказались полезными при решении ряда задач, обла дающих динамической симметрией.С их помощью были решены задачи о рождении пар частиц в однородном внешнем поле (4); когерентные со стояния для группы вращений (5) применялись для оценки статистиче ской суммы квантовой системы спинов (6) и в модели Дике (7).В этой заметке мы рассмотрим о.к.с., связанные с представлениями основной серии класса I. Особенно подробно будут рассмотрены о.к.с.для симметрических пространств трубчатого типа. 1. Пусть Gсвязная вещественная полупростая группа Ли с конеч ным центром.Известно (8), что группа G обладает серией унитарных не приводимых представлений (у.н.п.) класса I, т. е. серией у.н.п., в про странстве представления которых существует вектор | ф0>, инвариантный относительно действия максимальной компактной подгруппы К. Рассмотрим множество состояний {T(g) |-ф0>}; |i|?s>=7'(g) |ф0>.Такое состояние определяется точкой фактор-пространства X=G/K (X -сим метрическое пространство некомпактного типа).Выбирая в классе gK, соответствующем точке х^Х, элемент gx, получаем систему состояний {|а:>}:

•Jan 1, 1974•0 citations

Математические аспекты слабо неидеального бозе- и ферми-газа на кристаллической подложке

Виктор Павлович Маслов, Victor Pavlovich Maslov

Математические аспекты слабо неидеального бозе-и ферми-газа на кристаллической подложке c 2003.В. П. МАСЛОВ В современном функциональном анализе часто рассматриваются уравнения с частными производными от бесконечного числа аргументов в бесконечной области.Вопрос об асимптотике решений уравнений при стремящемся к бесконечности числе аргументов, если одновременно стремится к бесконечности «объем» области, на которой рассматривается задача, близок к задачам квантовой статистики и термодинамики.Эти задачи в физике так же, как и в квантовой теории поля, часто рассматриваются на решетке (на разностной сетке).Это делается не только для некоторых упрощений и регуляризаций, но и потому, что такая постановка реализуется в кристаллических структурах.С другой стороны, задачи квантовой статистики связаны с математической статистикой и теорией вероятностей.Известно, что квадрат модуля собственной функции уравнения Шрёдингера определяет плотность распределения частицы по координатам, отвечающую этому собственному значению, т. е. говоря на физическом языке, данному уровню энергии

Функциональный анализ и его приложения•Jan 1, 2003•15 citations

От Материи к Духу: Квантовая физика как тень Единого Потока

Григорий Кузнецов, Ярослав Кузнецов

В данной работе предлагается концептуальный мост между стандартной квантовой механикой и многомерной моделью «Поток». Мы постулируем, что фундаментальные физические формулы описывают лишь внешние проявления («тени») глубинных законов Мироздания, игнорируя роль Когерентного Центра (Наблюдателя). Путем декодирования ключевых уравнений квантовой физики через систему 16 Оптик, образы Буквицы и концепцию Инглии, показано, что фундаментальные константы являются математическим выражением духовных категорий: постоянная Планка ( h h) интерпретируется как квант Первичного Огня (Инглии), работа выхода ( ϕ ϕ) — как порог энтропии (Рок), а главное квантовое число ( n n) — как иерархия уровней Лада (мерностей сознания). Введено метафизическое расширение уравнения единства с фактором фазовой когерентности ( γ γ). Работа демонстрирует, что материя и дух не являются дуалистичными субстанциями, а представляют собой две фазы одного Единого Поля, переход между которыми управляется Законом Меры (КОН) и резонансной синхронизацией. Результаты могут быть использованы для расширения парадигмы в квантовой биологии, теории сознания и поисках единой теории поля.

•Aug 27, 2026•0 citations

От Материи к Духу: Квантовая физика как тень Единого Потока

Григорий Кузнецов, Ярослав Кузнецов

В данной работе предлагается концептуальный мост между стандартной квантовой механикой и многомерной моделью «Поток». Мы постулируем, что фундаментальные физические формулы описывают лишь внешние проявления («тени») глубинных законов Мироздания, игнорируя роль Когерентного Центра (Наблюдателя). Путем декодирования ключевых уравнений квантовой физики через систему 16 Оптик, образы Буквицы и концепцию Инглии, показано, что фундаментальные константы являются математическим выражением духовных категорий: постоянная Планка ( h h) интерпретируется как квант Первичного Огня (Инглии), работа выхода ( ϕ ϕ) — как порог энтропии (Рок), а главное квантовое число ( n n) — как иерархия уровней Лада (мерностей сознания). Введено метафизическое расширение уравнения единства с фактором фазовой когерентности ( γ γ). Работа демонстрирует, что материя и дух не являются дуалистичными субстанциями, а представляют собой две фазы одного Единого Поля, переход между которыми управляется Законом Меры (КОН) и резонансной синхронизацией. Результаты могут быть использованы для расширения парадигмы в квантовой биологии, теории сознания и поисках единой теории поля.

•Aug 27, 2026•1 citation

Перепутывание в модели Тависа-Каммингса при наличии керровской нелинейности

Осман А., Осман А., Башкиров Е. К.

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

•Jan 1, 2021•0 citations
А. А. Разборов О квантовой коммуникационной сложности симметрических предикатов С точностью до логарифмического множителя определяется коммуникацион ная сложность вычисления произвольной, зависящей лишь от \х П г/|, функции /(ж, г/), х,у С [п], с допустимой вероятностью ошибки, отделенной от 1/2.Бо лее точно, для предиката D на множестве {0,1,..., п} полагаемПолученный результат выполняется как в модели с предварительным зацеплением, так и в модели без такого зацепления.Библиография: 26 наименований.§ 1. Введение С момента, когда модель коммуникационной сложности была впервые рассмот рена в работе [25], она развилась в важное самостоятельное направление теории вычислительной сложности, позволяющее, в частности, взглянуть с единой точки зрения на целый ряд разнородных понятий.В этой модели участвуют два игро ка, по традиции называемые Алиса и Боб.У Алисы имеется некоторый элемент х из фиксированного конечного множества X, у Боба -другой элемент у £ F, и их задача состоит в вычислении некоторого (данного заранее) булевого предиката f: X xY ^ {0,1} путем обмена сообщениями.Сложность измеряется суммарной битовой длиной пересланных сообщений, и так же, как и во многих других разде лах теории вычислительной сложности, при этом различают детерминированные и вероятностные алгоритмы.Точно так же, как в теории сложности булевых схем часто рассматривают симметрические булевы функции, значительный интерес в теории коммуникаци онной сложности представляют симметрические предикаты, определяемые как такие /, для которых хну -конечные множества и значение / задается формулой Работа выполнена во время командировки в Институт перспективных исследований (Принстон, США), поддержанной Фондом им.фон Неймана.
в. ГЕЙЗЕНБЕРГ что они напоминают те парадоксы, которые появились при анализе явлений излучения.Отказ от пространственно-временных образов характерен для формального рассмотрения проблем теории излучения и механической теории теплоты.Подобное рассмотрение было предпринято в недавно появившихся работах де Бройля *) и Эйнштейна **).С точки зрения' перспективы, которую открывают эти работы, я считал бы, что содержащиеся в настоящей работе соображения могут иметь некоторый интерес.Поэтому я решил опубликовать эту работу без изменений, хотя лежащие в ее основе стремления теперь могут показаться, пожалуй, безнадежными.530.145.6 О КВАНТОВОТЕОРЕТИЧЕСКОМ ИСТОЛКОВАНИИ КИНЕМАТИЧЕСКИХ И МЕХАНИЧЕСКИХ СООТНОШЕНИЙ***) В. Гейзенберг (Гёттинген) (Поступило 29 июля 1925 г.) В этой работе делается попытка получить основы квантовотеоретической механики, которые базируются исключительно на соотношениях между принципиально наблюдаемыми величинами.Как широко известно, против формальных правил, которые используются в квантовой теории для вычисления наблюдаемых величин (например, энергии водородного атома), выдвигаются серьезные возражения: эти правила содержат в качестве существенной составной части отношения между величинами, которые, по-видимому, принципиально не могут быть наблюдаемы (каковы, например, положение и время обращения электрона).Таким образом, этим правилам явно недостает какого-либо наглядного физического фундамента, если все еще не придерживаться надежды, что такие до сих пор ненаблюдаемые величины, возможно, могут стать доступными эксперименту когда-либо позднее.Такая надежда могла бы считаться правомерной, если бы упомянутые правила были сами по себе последовательны и применимы в какой-либо определенной ограниченной области квантовотеоретических проблем.Но опыт показывает, что эти формальные правила квантовой теории пригодны только для задач об атоме водорода и его эффекте Штарка, но уже в задаче о «скрещенных полях» («gekreuzten Felder») (атом водорода в электрическом и магнитном полях различного направления) появляются фундаментальные трудности, состоящие в том, что взаимодействие атома с периодически меняющимися полями, несомненно, не может удовлетворительно описываться с помощью названных правил и, что, наконец, распространение этих правил на описание атомов со многими электронами оказалось невозможным.Стало обычным считать эти неудачи квантовотеоретических правил, которые ведь по-существу, характеризовались применением классической механики, как отклонение от классической механики.Но
МАТЕМАТИЧЕСКАЯ ФИЗИКА М. И. МОНАСТЫРСКИЙ, А. М. ПЕРЕЛОМОВ КОГЕРЕНТНЫЕ СОСТОЯНИЯ ДЛЯ ГРУПП ДВИЖЕНИЙ СИММЕТРИЧЕСКИХ ПРОСТРАНСТВ (Представлено академиком Я. Б. Зельдовичем 22 II 1974) В настоящей работе мы продолжим начатое в (*) исследование обоб щенных когерентных состояний (о.к.с.), не являющихся квадратично-интегрируемыми.О.к.с., введенные в (2), так же как и обычные когерент ные состояния (3), оказались полезными при решении ряда задач, обла дающих динамической симметрией.С их помощью были решены задачи о рождении пар частиц в однородном внешнем поле (4); когерентные со стояния для группы вращений (5) применялись для оценки статистиче ской суммы квантовой системы спинов (6) и в модели Дике (7).В этой заметке мы рассмотрим о.к.с., связанные с представлениями основной серии класса I. Особенно подробно будут рассмотрены о.к.с.для симметрических пространств трубчатого типа. 1. Пусть Gсвязная вещественная полупростая группа Ли с конеч ным центром.Известно (8), что группа G обладает серией унитарных не приводимых представлений (у.н.п.) класса I, т. е. серией у.н.п., в про странстве представления которых существует вектор | ф0>, инвариантный относительно действия максимальной компактной подгруппы К. Рассмотрим множество состояний {T(g) |-ф0>}; |i|?s>=7'(g) |ф0>.Такое состояние определяется точкой фактор-пространства X=G/K (X -сим метрическое пространство некомпактного типа).Выбирая в классе gK, соответствующем точке х^Х, элемент gx, получаем систему состояний {|а:>}:
Математические аспекты слабо неидеального бозе-и ферми-газа на кристаллической подложке c 2003.В. П. МАСЛОВ В современном функциональном анализе часто рассматриваются уравнения с частными производными от бесконечного числа аргументов в бесконечной области.Вопрос об асимптотике решений уравнений при стремящемся к бесконечности числе аргументов, если одновременно стремится к бесконечности «объем» области, на которой рассматривается задача, близок к задачам квантовой статистики и термодинамики.Эти задачи в физике так же, как и в квантовой теории поля, часто рассматриваются на решетке (на разностной сетке).Это делается не только для некоторых упрощений и регуляризаций, но и потому, что такая постановка реализуется в кристаллических структурах.С другой стороны, задачи квантовой статистики связаны с математической статистикой и теорией вероятностей.Известно, что квадрат модуля собственной функции уравнения Шрёдингера определяет плотность распределения частицы по координатам, отвечающую этому собственному значению, т. е. говоря на физическом языке, данному уровню энергии
В данной работе предлагается концептуальный мост между стандартной квантовой механикой и многомерной моделью «Поток». Мы постулируем, что фундаментальные физические формулы описывают лишь внешние проявления («тени») глубинных законов Мироздания, игнорируя роль Когерентного Центра (Наблюдателя). Путем декодирования ключевых уравнений квантовой физики через систему 16 Оптик, образы Буквицы и концепцию Инглии, показано, что фундаментальные константы являются математическим выражением духовных категорий: постоянная Планка ( h h) интерпретируется как квант Первичного Огня (Инглии), работа выхода ( ϕ ϕ) — как порог энтропии (Рок), а главное квантовое число ( n n) — как иерархия уровней Лада (мерностей сознания). Введено метафизическое расширение уравнения единства с фактором фазовой когерентности ( γ γ). Работа демонстрирует, что материя и дух не являются дуалистичными субстанциями, а представляют собой две фазы одного Единого Поля, переход между которыми управляется Законом Меры (КОН) и резонансной синхронизацией. Результаты могут быть использованы для расширения парадигмы в квантовой биологии, теории сознания и поисках единой теории поля.
В данной работе предлагается концептуальный мост между стандартной квантовой механикой и многомерной моделью «Поток». Мы постулируем, что фундаментальные физические формулы описывают лишь внешние проявления («тени») глубинных законов Мироздания, игнорируя роль Когерентного Центра (Наблюдателя). Путем декодирования ключевых уравнений квантовой физики через систему 16 Оптик, образы Буквицы и концепцию Инглии, показано, что фундаментальные константы являются математическим выражением духовных категорий: постоянная Планка ( h h) интерпретируется как квант Первичного Огня (Инглии), работа выхода ( ϕ ϕ) — как порог энтропии (Рок), а главное квантовое число ( n n) — как иерархия уровней Лада (мерностей сознания). Введено метафизическое расширение уравнения единства с фактором фазовой когерентности ( γ γ). Работа демонстрирует, что материя и дух не являются дуалистичными субстанциями, а представляют собой две фазы одного Единого Поля, переход между которыми управляется Законом Меры (КОН) и резонансной синхронизацией. Результаты могут быть использованы для расширения парадигмы в квантовой биологии, теории сознания и поисках единой теории поля.
Актуальность темы. В настоящее время хорошо изучено коллективное поведение одиночного атома и пары атомов , во взаимодействии с квантованным полем в резонаторе, а эволюция двух кубитов моделей изучена в значительно меньшей степени. Вместе с тем известно, что чем больше частиц взаимодействует, тем более полезной такая система является для квантовых приложений. Цель работы: изучение динамики перепутывания двух дипольно- связанных сверхпроводящих кубитов, взаимодействующих с одномодовым квантовым электромагнитным полем копланарного идеального резонатора со средой Керра для различных начальных состояний кубитов и поля.