1. Результаты сложности для задачи о несоответствии Уивера (arXiv)

Автор:Дэниел А. Спилман, Пэн Чжан

Аннотация:Маркус, Спилман и Сривастава [MSS15] решили проблему Кадисона–Зингера, доказав сильную форму гипотезы Уивера: они показали, что для всех √α › 0 и всех списков векторов нормы не более √α, сумма внешних произведений которых равна единице, существует знаковая сумма этих внешних произведений с операторной нормой не более √8α + 2α. Доказано, что NP-трудно отличить такой список векторов, для которых существует сумма со знаком, равная нулевой матрице, от тех, в которых каждая сумма со знаком имеет операторную норму не менее κ√α, для некоторой абсолютной константы κ > 0. Таким образом, NP-сложно построить знак, который является постоянным множителем лучше, чем тот, который гарантированно существует. Для α = 1/4 мы доказываем, что NP-трудно различить, существует ли сумма со знаком, равная нулю матрица из случая, когда каждая сумма со знаком имеет операторную норму не менее 1/4.

2.Квантовое телеклонирование на компьютерах NISQ (arXiv)

Автор: Элайджа Пелофске, Андреас Бэрчи, Брайан Гарсия, Борис Кифер, Стефан Эйденбенц

Аннотация: Из-за теоремы о запрете клонирования создание идеальных квантовых клонов произвольного квантового состояния невозможно, однако приблизительные квантовые клоны могут быть созданы. Квантовое телеклонирование — это протокол, основанный на сочетании квантовой телепортации и квантового клонирования. Здесь мы представляем схемы квантового телеклонирования 1 → 2 и 1 → 3, со вспомогательными средствами и без них, которые теоретически оптимальны (это означает, что клоны имеют наивысшую точность, допускаемую квантовой механикой), универсальны (это означает, что точность клонирования не зависит от клонируемого состояния). ) и симметричный (это означает, что все клоны имеют одинаковую точность). Мы реализуем эти схемы на аппаратных средствах IBMQ и Quantinuum NISQ модели ворот и количественно оцениваем точность клонирования с помощью параллельной томографии состояния одного кубита. Квантовое телеклонирование с использованием измерения средней цепи в режиме реального времени, если заявления демонстрируются на устройстве Quantinuum H1–2. Две альтернативные реализации квантового телеклонирования (отложенное измерение и пост-выборка) демонстрируются на ibmq montreal для случаев, когда промежуточное измерение в режиме реального времени, если операторы недоступны. Наши результаты показывают, что устройства NISQ могут достигать почти оптимальной точности квантового телеклонирования; например, устройство Quantinuum H1–2, работающее со схемами телеклонирования без помощника, достигло средней точности клонирования 0,824 для двух схем клонирования и 0,765 для трех схем клонирования (теоретические пределы точности составляют 0,833 для двух клонов и 0,77 для трех клонов). Это демонстрирует жизнеспособность проведения экспериментального анализа квантовых информационных сетей и протоколов квантовой криптографии на компьютерах NISQ.

3.Динамические структуры данных для задач с параметризованными строками(arXiv)

Автор:Енджей Ольковски, Михал Пилипчук, Матеуш Рыхлицкий, Кароль Венгжицкий, Анна Зых-Павлевич

Аннотация: мы возвращаемся к классическим задачам со строками, рассматриваемыми в области параметризованной сложности, и изучаем их через призму динамических структур данных. То есть вместо того, чтобы запрашивать статический алгоритм, который эффективно решает данный экземпляр, наша цель состоит в том, чтобы разработать структуру данных, которая эффективно поддерживает решение или сообщает об его отсутствии при обновлениях в экземпляре. Сначала мы рассмотрим проблему ближайшей строки. , для которых мы разрабатываем рандомизированные динамические структуры данных с амортизированным временем обновления dO(d) и |Σ|O(d) соответственно, где Σ — алфавит, а d — предполагаемая граница максимального расстояния. Они получены путем объединения известных статических подходов к ближайшей строке с цветовым кодированием. Далее мы отмечаем, что из результата Frandsen et al. [Дж. ACM'97] можно легко вывести метатеорему, которая обеспечивает динамические структуры данных для задач с параметризованными строками с временем обновления в наихудшем случае в форме Ok(loglogn), где k — рассматриваемый параметр, а n — длина строки. . Мы демонстрируем полезность этой метатеоремы, предоставляя такие структуры данных для задач Непересекающиеся факторы и Расстояние редактирования. Мы также приводим явные структуры данных для этих задач с временем обновления в наихудшем случае O(k2k log log n) и O(k2 log log n) соответственно. Наконец, мы обсудим, как методология нижней границы, представленная Amarilli et al. [ICALP’21] можно использовать, чтобы показать, что получение времени обновления O(f(k)) для непересекающихся факторов и расстояния редактирования маловероятно уже при постоянном значении параметра k.

4.Лемма Джонсона-Линденштрауса для кластеризации и аппроксимации подпространств: от базовых наборов к уменьшению размерности (arXiv)

Автор:Моисей Чарикар, Эрик Вайнгартен

Аннотация: мы изучаем влияние преобразований Джонсона-Линденштрауса на различные задачи евклидовой оптимизации. Мы спрашиваем, для конкретной задачи и параметра точности ε ∈ (0, 1), какова наименьшая целевая размерность t ∈ рот, такая, что преобразование Джонсона-Линденштрауса Π: d → t сохраняет стоимость оптимального решения с точностью до a ( 1 + ε)-фактор.

  • Forcenter-based(k,z)-кластеризация, weshowt=O((logk+zlog(1/ε))/ε2) достаточна, улучшая O((log k + z log(1/ε) + z2)/ε2 ) [MMR19].
  • Покажем, что для приближения (k, z)-подпространства достаточно t = O ̃(zk2/ε3). Предыдущая наилучшая оценка O(k/ε2), применяемая только к случаю z = 2 [CEM+15]
  • Для (k,z)-плоской аппроксимации мы показываем, что t = O ̃(zk2/ε3) достаточно, улучшая оценку O ̃(zk2 log n/ε3) [KR15]
  • Для аппроксимации (k, z)-линии мы показываем, что t = O((k log log n + z + log(1/ε))/ε3) достаточно. Предыдущие результаты не были известны.

Все приведенные выше результаты следуют из одного общего приема: мы используем алгоритмы построения базисных наборов в качестве аналитического инструмента при рандомизированном снижении размерности.

5.О бинарной сетевой игре общественных благ с альтруизмом (arXiv)

Автор:Арнаб Маити, Палаш Дей

Выдержка. В классической игре Binary Networked Public Goods (BNPG) игрок может либо инвестировать в общественный проект, либо решить не инвестировать. На основании решений всех игроков каждый игрок получает вознаграждение в соответствии со своей функцией полезности. Однако классические модели игры BNPG не учитывают альтруизм, который часто проявляют игроки и который может существенно повлиять на равновесное поведение. Ю и др. [24] расширили классическую игру BNPG, чтобы отразить альтруистический аспект игроков. В этой статье мы сначала изучаем проблему определения существования равновесия Нэша в чистой стратегии (PSNE) в игре BNPG с альтруизмом. Уже известно, что эта задача является NP-полной. Мы дополняем этот результат сложности, показывая, что задача допускает эффективные алгоритмы, когда входная сеть является либо деревом, либо полным графом. Далее мы изучаем проблему модификации альтруистической сети, задача которой состоит в том, чтобы вычислить, можно ли сделать профиль целевой стратегии PSNE путем добавления или удаления нескольких ребер. Эта задача также известна как NP-полная. Мы усиливаем этот результат твердости, демонстрируя результаты неподатливости даже для деревьев. Возможно, неожиданным открытием нашей работы является то, что указанная выше проблема остается NP-трудной даже для графов с ограниченными степенями, когда сеть альтруизма ненаправлена, но становится разрешимой за полиномиальное время, когда сеть альтруизма направлена. Мы также показываем некоторые результаты вычисления MSNE и некоторые параметризованные результаты сложности. Таким образом, наши результаты показывают, что гораздо легче предсказать, как будут вести себя игроки в игре BNPG, по сравнению с тем, как игроков в игре BNPG можно заставить вести себя желаемым образом.