QIP2021 | QMA-твёрдость согласованности локальных матриц плотности с применением... (Алекс Бредар...

QMA-трудность задачи согласованности локальных матриц плотности с приложениями к квантовой теории нулевого разглашения Авторы: Энн Бродбент и Алекс Бредариол Грило Организации: Университет Оттавы | LIP6, CNRS/Сорбонна Аннотация Мы предлагаем ряд усовершенствований для понимания класса квантовых систем доказательств Мерлина-Артура (QMA), квантового аналога NP. Наш главный вклад заключается в доказательстве давней гипотезы о том, что задача согласованности локальных матриц плотности (CLDM) является QMA-трудной относительно редукций Карпа. Входные данные CLDM состоят из локальных редуцированных матриц плотности на множествах не более k кубитов, и задача заключается в том, существует ли глобальное квантовое состояние n-кубитов, локально согласованное со всеми k-кубитными локальными матрицами плотности. Содержание CLDM в QMA и QMA-трудность относительно редукций Тьюринга были доказаны Лю [APPROX-RANDOM 2006]. Лю также предположил, что CLDM является QMA-трудным относительно редукций Карпа, что желательно для приложений, и мы, наконец, доказали эту гипотезу. Мы устанавливаем этот результат, используя методы моделируемых кодов Грило, Слофстры и Юэня [FOCS 2019], упрощая их доказательства и адаптируя их к контексту QMA. Чтобы разработать приложения CLDM, мы предлагаем структуру, которую мы называем локально моделируемыми доказательствами для QMA: это обеспечивает доказательства QMA, которые могут быть эффективно проверены путем проверки только k кубитов, и, более того, редуцированная матрица плотности любой k-кубитной подсистемы хорошего свидетеля может быть вычислена за полиномиальное время независимо от свидетеля. В рамках этой структуры мы показываем несколько достижений в области нулевого разглашения в квантовой обстановке. Мы впервые демонстрируем систему доказательства с нулевым разглашением, основанную на принципе «коммита-и-открыто», для всего QMA как квантовый аналог протокола «сигма». Затем мы определяем доказательство квантового знания, которое гарантирует, что доказывающая сторона фактически обладает квантовым свидетельством в интерактивном доказательстве, и показываем, что наша система доказательства с нулевым разглашением удовлетворяет этому определению. Присоединяйтесь к нам! ▶ Конференция QIP2021: https://www.mcqst.de/qip2021 ▶ Веб-сайт: https://www.mcqst.de ▶ LinkedIn: https://www.linkedin.com/company/mcqst