[2307.09444] Нет распределенного квантового преимущества для приблизительной раскраски графа.

Загрузите PDF-файл статьи Ксавье Коите-Роя и еще 9 авторов под названием «Нет распределенного квантового преимущества для приблизительной раскраски графов».

Скачать PDF

Абстрактный:Дана практически полная характеристика сложности $c$-раскраски $chi$-хроматических графов с помощью распределенных алгоритмов для широкого круга моделей распределенных вычислений. В частности, мы показываем, что эти задачи не допускают какого-либо распределенного квантового преимущества. Для этого: 1) Мы даем новый распределенный алгоритм, который находит $c$-раскраску в $chi$-хроматических графах в $tilde{mathcal{O}}(n^{frac{1}{) Alpha}})$ раундов, с $alpha = bigllfloorfrac{c-1}{chi – 1}bigrrfloor$. 2) Мы доказываем, что любой распределенный алгоритм для этой задачи требует $Omega(n^{frac{1}{alpha}})$ раундов.

Наша верхняя граница справедлива для классической детерминированной ЛОКАЛЬНОЙ модели, тогда как почти совпадающая нижняя граница справедлива для модели без сигнализации. Эта модель, представленная Арфауи и Фраиньо в 2014 году, охватывает все модели алгоритмов распределенных графов, подчиняющихся физической причинности; это включает в себя не только классический детерминированный ЛОКАЛЬНЫЙ и рандомизированный ЛОКАЛЬНЫЙ, но и квантово-ЛОКАЛЬНЫЙ, даже с предварительно общим квантовым состоянием.

Мы также показываем, что аналогичные аргументы можно использовать, чтобы доказать, что, например, двумерные сетки с 3-раскраской или деревья с $c$-раскраской остаются трудными проблемами даже для модели без сигналов и, в частности, не допускают каких-либо квантовых преимуществ. Наши аргументы, связанные с нижней границей, по своей сути являются чисто теоретико-графовыми; для установления доказательств не требуется никаких знаний в области квантовой теории информации.