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

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

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

МАТЕМАТИЧЕСКАЯ ФИЗИКА М. И. МОНАСТЫРСКИЙ, А. М. ПЕРЕЛОМОВ КОГЕРЕНТНЫЕ СОСТОЯНИЯ ДЛЯ ГРУПП ДВИЖЕНИЙ СИММЕТРИЧЕСКИХ ПРОСТРАНСТВ (Представлено академиком Я. Б. Зельдовичем 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

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

Werner Karl Heisenberg

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

Uspekhi Fizicheskih Nauk•Jan 1, 1977•2 citations

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

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

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

•Aug 27, 2026•1 citation

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

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

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

•Aug 27, 2026•0 citations

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

Oleg Vasilevich Morzhin, Alexander Nikolaevich Pechen

Математические задачи оптимального управления квантовыми системами привлекают высокий интерес в связи как с фундаментальными проблемами физики, так и с существующими и перспективными приложениями для квантовых технологий. Важной проблемой является разработка методов построения управлений для квантовых систем. Одним из широко используемых методов является метод Кротова, предложенный изначально вне квантового управления в статьях В. Ф. Кротова и И. Н. Фельдмана (1978, 1983 гг.). Этот метод был применен для разработки нового подхода к построению оптимальных управлений для квантовых систем в работах [64] (D. J. Tannor, V. Kazakov, V. Orlov, 1992 г.), [65] (J. Somlói, V. A. Kazakov, D. J. Tannor, 1993 г.) и во многих других работах различных исследователей. Обзор посвящен математическим аспектам этого метода для оптимального управления замкнутыми квантовыми системами. Излагаются различные варианты метода, отличающиеся видом улучшающей функции (как правило, линейной или линейно-квадратичной), ограничениями на спектр управления и на состояния квантовой системы, регуляризаторами и т. д. Обзор описывает приложения метода Кротова к управлению молекулярной динамикой и конденсатом Бозе-Эйнштейна, а также к генерации квантовых вентилей. Проводится сравнение с методами GRAPE (GRadient Ascent Pulse Engineering), CRAB (Chopped Random-Basis), Чжу-Рабица и Мадея-Туриничи. Библиография: 158 названий.

Успехи математических наук•Sep 1, 2019•5 citations

А.И. Иванов, В.В. Березюк ПРОЯВЛЕНИЕ НЕАБЕЛЕВОЙ ГЕОМЕТРИЧЕСКОЙ ФАЗЫ В СИСТЕМАХ С КВАДРУПОЛЬНЫМ ВЗАИМОДЕЙСТВИЕМ Рассмотрен эксперимент Р. Тико по вращательному расщепле- нию линий в спектрах ЯКР. Показана связь этого расщепления с не- абелевой геометрической фазой. Вычисленная на основе КЭС вели- чина расщепления согласуется с ее экспериментальным значением.

Robert Tycko

Введение Несмотря на два десятилетия, прошедшие с момента публикации работы М. Берри [1], в которой было показано, что при достаточно мед-ленной эволюции квантовой системы полная фаза ее волновой функ-ции наряду с хорошо известным динамическим вкладом содержит сла-гаемое, имеющее геометрическую природу, интерес к этой теме как у теоретиков, так и у экспериментаторов не угас. Существенным про-движением на этом пути стало введение Ф. Вильчеком и А. Зи [2] не-абелевой геометрической фазы. Одним из наиболее важных результа-тов, способствовавших лучшему пониманию абелевой и неабелевой геометрических фаз, является предложение рассматривать фазу Берри как голономию связности линейного расслоения, относящуюся к невы-рожденным собственным состояниям гамильтониана [3]. Хотя уже выполнены сотни работ по геометрическим фазам, число детально рассмотренных примеров не так велико. Одним из примеров проявления геометрической фазы является эксперимент, описанный в работе Р. Тико «Адиабатическое враща-тельное расщепление и фаза Берри в ядерном квадрупольном резонан-се». В этой работе для демонстрации вращательного расщепления в спектрах ЯКР рассмотрен эксперимент с вращением образца. Расщеп-ление интерпретируется как проявление геометрической фазы, обу-словленной адиабатически меняющимся гамильтонианом. Данная ста-тья посвящена детальному рассмотрению эксперимента Р. Тико и при-менению подхода Ф. Вильчека и А. Зи к расчету геометрической фазы.

•Jan 1, 2006•0 citations
А. А. Разборов О квантовой коммуникационной сложности симметрических предикатов С точностью до логарифмического множителя определяется коммуникацион ная сложность вычисления произвольной, зависящей лишь от \х П г/|, функции /(ж, г/), х,у С [п], с допустимой вероятностью ошибки, отделенной от 1/2.Бо лее точно, для предиката D на множестве {0,1,..., п} полагаемПолученный результат выполняется как в модели с предварительным зацеплением, так и в модели без такого зацепления.Библиография: 26 наименований.§ 1. Введение С момента, когда модель коммуникационной сложности была впервые рассмот рена в работе [25], она развилась в важное самостоятельное направление теории вычислительной сложности, позволяющее, в частности, взглянуть с единой точки зрения на целый ряд разнородных понятий.В этой модели участвуют два игро ка, по традиции называемые Алиса и Боб.У Алисы имеется некоторый элемент х из фиксированного конечного множества X, у Боба -другой элемент у £ F, и их задача состоит в вычислении некоторого (данного заранее) булевого предиката f: X xY ^ {0,1} путем обмена сообщениями.Сложность измеряется суммарной битовой длиной пересланных сообщений, и так же, как и во многих других разде лах теории вычислительной сложности, при этом различают детерминированные и вероятностные алгоритмы.Точно так же, как в теории сложности булевых схем часто рассматривают симметрические булевы функции, значительный интерес в теории коммуникаци онной сложности представляют симметрические предикаты, определяемые как такие /, для которых хну -конечные множества и значение / задается формулой Работа выполнена во время командировки в Институт перспективных исследований (Принстон, США), поддержанной Фондом им.фон Неймана.
МАТЕМАТИЧЕСКАЯ ФИЗИКА М. И. МОНАСТЫРСКИЙ, А. М. ПЕРЕЛОМОВ КОГЕРЕНТНЫЕ СОСТОЯНИЯ ДЛЯ ГРУПП ДВИЖЕНИЙ СИММЕТРИЧЕСКИХ ПРОСТРАНСТВ (Представлено академиком Я. Б. Зельдовичем 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, получаем систему состояний {|а:>}:
в. ГЕЙЗЕНБЕРГ что они напоминают те парадоксы, которые появились при анализе явлений излучения.Отказ от пространственно-временных образов характерен для формального рассмотрения проблем теории излучения и механической теории теплоты.Подобное рассмотрение было предпринято в недавно появившихся работах де Бройля *) и Эйнштейна **).С точки зрения' перспективы, которую открывают эти работы, я считал бы, что содержащиеся в настоящей работе соображения могут иметь некоторый интерес.Поэтому я решил опубликовать эту работу без изменений, хотя лежащие в ее основе стремления теперь могут показаться, пожалуй, безнадежными.530.145.6 О КВАНТОВОТЕОРЕТИЧЕСКОМ ИСТОЛКОВАНИИ КИНЕМАТИЧЕСКИХ И МЕХАНИЧЕСКИХ СООТНОШЕНИЙ***) В. Гейзенберг (Гёттинген) (Поступило 29 июля 1925 г.) В этой работе делается попытка получить основы квантовотеоретической механики, которые базируются исключительно на соотношениях между принципиально наблюдаемыми величинами.Как широко известно, против формальных правил, которые используются в квантовой теории для вычисления наблюдаемых величин (например, энергии водородного атома), выдвигаются серьезные возражения: эти правила содержат в качестве существенной составной части отношения между величинами, которые, по-видимому, принципиально не могут быть наблюдаемы (каковы, например, положение и время обращения электрона).Таким образом, этим правилам явно недостает какого-либо наглядного физического фундамента, если все еще не придерживаться надежды, что такие до сих пор ненаблюдаемые величины, возможно, могут стать доступными эксперименту когда-либо позднее.Такая надежда могла бы считаться правомерной, если бы упомянутые правила были сами по себе последовательны и применимы в какой-либо определенной ограниченной области квантовотеоретических проблем.Но опыт показывает, что эти формальные правила квантовой теории пригодны только для задач об атоме водорода и его эффекте Штарка, но уже в задаче о «скрещенных полях» («gekreuzten Felder») (атом водорода в электрическом и магнитном полях различного направления) появляются фундаментальные трудности, состоящие в том, что взаимодействие атома с периодически меняющимися полями, несомненно, не может удовлетворительно описываться с помощью названных правил и, что, наконец, распространение этих правил на описание атомов со многими электронами оказалось невозможным.Стало обычным считать эти неудачи квантовотеоретических правил, которые ведь по-существу, характеризовались применением классической механики, как отклонение от классической механики.Но
В данной работе предлагается концептуальный мост между стандартной квантовой механикой и многомерной моделью «Поток». Мы постулируем, что фундаментальные физические формулы описывают лишь внешние проявления («тени») глубинных законов Мироздания, игнорируя роль Когерентного Центра (Наблюдателя). Путем декодирования ключевых уравнений квантовой физики через систему 16 Оптик, образы Буквицы и концепцию Инглии, показано, что фундаментальные константы являются математическим выражением духовных категорий: постоянная Планка ( h h) интерпретируется как квант Первичного Огня (Инглии), работа выхода ( ϕ ϕ) — как порог энтропии (Рок), а главное квантовое число ( n n) — как иерархия уровней Лада (мерностей сознания). Введено метафизическое расширение уравнения единства с фактором фазовой когерентности ( γ γ). Работа демонстрирует, что материя и дух не являются дуалистичными субстанциями, а представляют собой две фазы одного Единого Поля, переход между которыми управляется Законом Меры (КОН) и резонансной синхронизацией. Результаты могут быть использованы для расширения парадигмы в квантовой биологии, теории сознания и поисках единой теории поля.
В данной работе предлагается концептуальный мост между стандартной квантовой механикой и многомерной моделью «Поток». Мы постулируем, что фундаментальные физические формулы описывают лишь внешние проявления («тени») глубинных законов Мироздания, игнорируя роль Когерентного Центра (Наблюдателя). Путем декодирования ключевых уравнений квантовой физики через систему 16 Оптик, образы Буквицы и концепцию Инглии, показано, что фундаментальные константы являются математическим выражением духовных категорий: постоянная Планка ( h h) интерпретируется как квант Первичного Огня (Инглии), работа выхода ( ϕ ϕ) — как порог энтропии (Рок), а главное квантовое число ( n n) — как иерархия уровней Лада (мерностей сознания). Введено метафизическое расширение уравнения единства с фактором фазовой когерентности ( γ γ). Работа демонстрирует, что материя и дух не являются дуалистичными субстанциями, а представляют собой две фазы одного Единого Поля, переход между которыми управляется Законом Меры (КОН) и резонансной синхронизацией. Результаты могут быть использованы для расширения парадигмы в квантовой биологии, теории сознания и поисках единой теории поля.
Математические задачи оптимального управления квантовыми системами привлекают высокий интерес в связи как с фундаментальными проблемами физики, так и с существующими и перспективными приложениями для квантовых технологий. Важной проблемой является разработка методов построения управлений для квантовых систем. Одним из широко используемых методов является метод Кротова, предложенный изначально вне квантового управления в статьях В. Ф. Кротова и И. Н. Фельдмана (1978, 1983 гг.). Этот метод был применен для разработки нового подхода к построению оптимальных управлений для квантовых систем в работах [64] (D. J. Tannor, V. Kazakov, V. Orlov, 1992 г.), [65] (J. Somlói, V. A. Kazakov, D. J. Tannor, 1993 г.) и во многих других работах различных исследователей. Обзор посвящен математическим аспектам этого метода для оптимального управления замкнутыми квантовыми системами. Излагаются различные варианты метода, отличающиеся видом улучшающей функции (как правило, линейной или линейно-квадратичной), ограничениями на спектр управления и на состояния квантовой системы, регуляризаторами и т. д. Обзор описывает приложения метода Кротова к управлению молекулярной динамикой и конденсатом Бозе-Эйнштейна, а также к генерации квантовых вентилей. Проводится сравнение с методами GRAPE (GRadient Ascent Pulse Engineering), CRAB (Chopped Random-Basis), Чжу-Рабица и Мадея-Туриничи. Библиография: 158 названий.
А.И. Иванов, В.В. Березюк ПРОЯВЛЕНИЕ НЕАБЕЛЕВОЙ ГЕОМЕТРИЧЕСКОЙ ФАЗЫ В СИСТЕМАХ С КВАДРУПОЛЬНЫМ ВЗАИМОДЕЙСТВИЕМ Рассмотрен эксперимент Р. Тико по вращательному расщепле- нию линий в спектрах ЯКР. Показана связь этого расщепления с не- абелевой геометрической фазой. Вычисленная на основе КЭС вели- чина расщепления согласуется с ее экспериментальным значением.
Введение Несмотря на два десятилетия, прошедшие с момента публикации работы М. Берри [1], в которой было показано, что при достаточно мед-ленной эволюции квантовой системы полная фаза ее волновой функ-ции наряду с хорошо известным динамическим вкладом содержит сла-гаемое, имеющее геометрическую природу, интерес к этой теме как у теоретиков, так и у экспериментаторов не угас. Существенным про-движением на этом пути стало введение Ф. Вильчеком и А. Зи [2] не-абелевой геометрической фазы. Одним из наиболее важных результа-тов, способствовавших лучшему пониманию абелевой и неабелевой геометрических фаз, является предложение рассматривать фазу Берри как голономию связности линейного расслоения, относящуюся к невы-рожденным собственным состояниям гамильтониана [3]. Хотя уже выполнены сотни работ по геометрическим фазам, число детально рассмотренных примеров не так велико. Одним из примеров проявления геометрической фазы является эксперимент, описанный в работе Р. Тико «Адиабатическое враща-тельное расщепление и фаза Берри в ядерном квадрупольном резонан-се». В этой работе для демонстрации вращательного расщепления в спектрах ЯКР рассмотрен эксперимент с вращением образца. Расщеп-ление интерпретируется как проявление геометрической фазы, обу-словленной адиабатически меняющимся гамильтонианом. Данная ста-тья посвящена детальному рассмотрению эксперимента Р. Тико и при-менению подхода Ф. Вильчека и А. Зи к расчету геометрической фазы.