Скрытая проблема сопоставления

Проблема скрытого сопоставления — это проблема сложности вычислений, которую можно решить с помощью квантовых протоколов: пусть $n$ быть положительным четным целым числом. В задаче о скрытом совпадении Алисе дается $x\in \{0,1\}^{n}$ и Бобу дан $M\in {\mathcal {M}}_{n}$ ( ${\mathcal {M}}_{n}$ обозначает семейство всех возможных совершенных паросочетаний на $n$ узлы). Их цель — вывести кортеж $\langle i,j,b\rangle$ такой, что край $(i,j)$ принадлежит к соответствующему $M$ и $b=x_{i}\oplus x_{j}$ . ^[1]

Он использовался для поиска задач квантовой связи, демонстрирующих суперполиномиальное преимущество над классическими. ^[1]^[2]^[3]

Фон

Сложность коммуникации — это модель вычислений, впервые представленная Яо в 1979 году. ^[4] Две стороны (обычно называемые Алисой и Бобом) каждая хранят фрагмент данных и хотят решить некоторую вычислительную задачу, которая совместно зависит от их данных. ^[3] Алиса знает только информацию $x$ а Боб знает только информацию $y$ , и они хотят решить какую-то функцию $f(x,y)$ . Для этого им необходимо будет общаться между собой, и их цель — решить проблему с минимальным общением, подчиняясь ограничениям конкретной модели общения.

Можно рассмотреть две ключевые модели коммуникации: ^[2]

Односторонняя связь — это модель, в которой Алиса отправляет одно сообщение Бобу, который должен дать ответ в зависимости от содержания сообщения и его части ввода.
Интерактивное (двустороннее) общение — это модель, в которой игроки могут в интерактивном режиме обмениваться сообщениями, пока Боб не решит дать ответ, на основе стенограммы общения и его части ввода.

Коммуникационные задачи могут быть либо функциональными, что означает, что каждому возможному вводу соответствует ровно один правильный ответ, либо реляционными, когда допускается несколько правильных ответов. ^[2]

История

Проблема скрытого сопоставления была впервые сформулирована в 2004 году Бар-Йосефом, Джайрамом и Керенидисом. ^[1] Благодаря его определению они смогли обеспечить первое экспоненциальное разделение между квантовой сложностью и сложностью рандомизированной односторонней связи с ограниченной ошибкой. Они доказали, что сложность квантовой односторонней связи в задаче скрытого сопоставления равна ${\mathcal {O}}(\log n)$ , однако любой рандомизированный односторонний протокол с ограниченной ошибкой должен использовать $\Omega ({\sqrt {n}})$ кусочки общения. Проблема скрытого соответствия — это реляционная проблема.

Алиса отправляет суперпозицию ${\frac {1}{\sqrt {n}}}\sum _{i=1}^{n}(-1)^{x_{i}}|i\rangle$ Бобу. Боб использует свое идеальное сопоставление, чтобы проецировать это квантовое состояние на один из n/2 ортогональных двумерных проекторов, причем проектор — на пространство, охватываемое $\{|i\rangle ,|j\rangle \}$ для спаривания i и j. После измерения квантовое состояние определяется измеряемым проектором. Бит b определяет, является ли результирующее состояние ${\frac {1}{\sqrt {2}}}\left(|i\rangle \pm |j\rangle \right)$ .

В классическом сообщении Алиса должна отправить по команде ${\mathcal {O}}\left({\sqrt {n}}\right)$ биты информации, определяющие значение x для такого количества узлов. В соответствии с проблемой дня рождения вероятность близка к 1, что хотя бы два узла в этом подмножестве соединены ребром.

В той же статье авторы предложили булеву версию проблемы — булеву проблему скрытого сопоставления — и предположили, что и для нее справедлив тот же квантово-классический разрыв. ^[1] Позже это было подтверждено Гавински и др. ^[5]

В 2008 году Гавинский еще больше улучшил результат Бар-Йосефа и др., показав экспоненциальное разделение между односторонней квантовой связью и двусторонней классической связью. ^[2]

Приложения

Скрытая проблема сопоставления была использована в качестве основы схемы квантовых монет Гавинского 2012 года . ^[6] Бобу дали монету в качестве оплаты за какой-то товар или услугу. Эта монета состоит из квантового регистра, содержащего несколько кубитов . Боб желает убедиться в подлинности монеты.

В классическом сценарии цифровая монета состоит из уникальной строки классических битов, держатель монет отправляет эту строку в банк, и банк сравнивает ее со статической базой данных действительных строк. Если строка существует в базе данных, банк подтверждает, что монета действительна. Однако это оставляет злоумышленнику возможность замаскироваться под банк и украсть монету держателя монет под предлогом ее проверки.

Используя проблему скрытого сопоставления, держатель монеты может отправить соответствующую информацию в банк, и банк может проверить, что монета подлинность, но злоумышленник, маскирующийся под банк, не узнает достаточно, чтобы иметь возможность воспроизвести монету.

В протоколе Боб предоставит значения $(a_{i},b_{i})$ в банк. Эти ценности $(a_{i},b_{i})$ достигаются тем, что Боб измеряет определенные квантовые регистры в своей монете. Банк хранит ценности $x_{i}$ (классические битовые строки) и $m_{i}$ . Если $\forall i\;(x_{i},m_{i},a_{i},b_{i})\in {\textit {HMP}}_{4}$ , то банк может проверить, что у Боба действительно есть действительная монета, соответствующая классическим значениям $x_{i}$ .

Для $x\in \{0,1\}^{4}$ и $m,a,b\in \{0,1\}$ , мы говорим, что $(x,m,a,b)\in {\textit {HMP}}_{4}$ если

$b={\begin{cases}x_{1}\otimes x_{2+m},\quad {\text{if }}a=0\\x_{3-m}\otimes x_{4},\quad {\text{if }}a=1,\end{cases}}$

${\textit {HMP}}_{4}$ относится к четырехбитной версии проблемы скрытого сопоставления.

Ссылки

^ Jump up to: ^а ^б ^с ^д Бар-Йосеф, Зив; Джайрам, Т.С.; Керенидис, Иорданис (13 июня 2004 г.). «Экспоненциальное разделение сложности квантовой и классической односторонней связи» . Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений . СТОК '04. Чикаго, Иллинойс, США: Ассоциация вычислительной техники. стр. 128–137. дои : 10.1145/1007352.1007379 . ISBN 978-1-58113-852-8 . S2CID 557748 .
^ Jump up to: ^а ^б ^с ^д Гавинский, Дмитрий (17 мая 2008 г.). «Классическое взаимодействие не может заменить квантовое сообщение» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Виктория, Британская Колумбия, Канада: Ассоциация вычислительной техники. стр. 95–102. дои : 10.1145/1374376.1374393 . ISBN 978-1-60558-047-0 . S2CID 6659329 .
^ Jump up to: ^а ^б Доригуэльо, Жоау Ф. (2020). «Экспоненциальные сокращения квантовой связи на основе обобщения булевой задачи скрытого сопоставления» (PDF) . 15-я конференция по теории квантовых вычислений, связи и криптографии (TQC 2020) . Международные труды Лейбница по информатике (LIPIcs). 158 : 1:1–1:16. arXiv : 2001.05553 . doi : 10.4230/LIPIcs.TQC.2020.1 . ISBN 9783959771467 . S2CID 210701354 .
^ Яо, Эндрю Чи-Чи (30 апреля 1979 г.). «Некоторые сложные вопросы, связанные с распределительными вычислениями (предварительный отчет)». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений - STOC '79 . Атланта, Джорджия, США: Ассоциация вычислительной техники. стр. 209–213. дои : 10.1145/800135.804414 . ISBN 978-1-4503-7438-5 . S2CID 999287 .
^ Гавинский Дмитрий; Кемпе, Джулия; Керенидис, Иорданис; Раз, Ран; де Вольф, Рональд (11 июня 2007 г.). «Экспоненциальные разделения для сложности односторонней квантовой связи с приложениями к криптографии» . Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . СТОК '07. Сан-Диего, Калифорния, США: Ассоциация вычислительной техники. стр. 516–525. дои : 10.1145/1250790.1250866 . ISBN 978-1-59593-631-8 . S2CID 444057 .
^ Гавинский, Д. (июнь 2012 г.). «Квантовые деньги с классической проверкой» . 27-я конференция IEEE по сложности вычислений , 2012 г. стр. 42–52. arXiv : 1109.0372 . дои : 10.1109/CCC.2012.10 . ISBN 978-0-7695-4708-4 . S2CID 11673644 .

[:0-1] Jump up to: ^а ^б ^с ^д Бар-Йосеф, Зив; Джайрам, Т.С.; Керенидис, Иорданис (13 июня 2004 г.). «Экспоненциальное разделение сложности квантовой и классической односторонней связи» . Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений . СТОК '04. Чикаго, Иллинойс, США: Ассоциация вычислительной техники. стр. 128–137. дои : 10.1145/1007352.1007379 . ISBN 978-1-58113-852-8 . S2CID 557748 .

[:1-2] Jump up to: ^а ^б ^с ^д Гавинский, Дмитрий (17 мая 2008 г.). «Классическое взаимодействие не может заменить квантовое сообщение» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Виктория, Британская Колумбия, Канада: Ассоциация вычислительной техники. стр. 95–102. дои : 10.1145/1374376.1374393 . ISBN 978-1-60558-047-0 . S2CID 6659329 .

[:2-3] Jump up to: ^а ^б Доригуэльо, Жоау Ф. (2020). «Экспоненциальные сокращения квантовой связи на основе обобщения булевой задачи скрытого сопоставления» (PDF) . 15-я конференция по теории квантовых вычислений, связи и криптографии (TQC 2020) . Международные труды Лейбница по информатике (LIPIcs). 158 : 1:1–1:16. arXiv : 2001.05553 . doi : 10.4230/LIPIcs.TQC.2020.1 . ISBN 9783959771467 . S2CID 210701354 .

[4] Яо, Эндрю Чи-Чи (30 апреля 1979 г.). «Некоторые сложные вопросы, связанные с распределительными вычислениями (предварительный отчет)». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений - STOC '79 . Атланта, Джорджия, США: Ассоциация вычислительной техники. стр. 209–213. дои : 10.1145/800135.804414 . ISBN 978-1-4503-7438-5 . S2CID 999287 .

[5] Гавинский Дмитрий; Кемпе, Джулия; Керенидис, Иорданис; Раз, Ран; де Вольф, Рональд (11 июня 2007 г.). «Экспоненциальные разделения для сложности односторонней квантовой связи с приложениями к криптографии» . Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . СТОК '07. Сан-Диего, Калифорния, США: Ассоциация вычислительной техники. стр. 516–525. дои : 10.1145/1250790.1250866 . ISBN 978-1-59593-631-8 . S2CID 444057 .

[6] Гавинский, Д. (июнь 2012 г.). «Квантовые деньги с классической проверкой» . 27-я конференция IEEE по сложности вычислений , 2012 г. стр. 42–52. arXiv : 1109.0372 . дои : 10.1109/CCC.2012.10 . ISBN 978-0-7695-4708-4 . S2CID 11673644 .

[1]

[2]

[3]

[4]

[5]

[6]