On the satisfiability of quantum circuits of small treewidth

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F17%3A00476160" target="_blank" >RIV/67985840:_____/17:00476160 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00224-016-9727-8" target="_blank" >http://dx.doi.org/10.1007/s00224-016-9727-8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00224-016-9727-8" target="_blank" >10.1007/s00224-016-9727-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the satisfiability of quantum circuits of small treewidth

Popis výsledku v původním jazyce

It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time ... a classical assignment ... that maximizes the acceptance probability of C up to a delta additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)... For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t = O(logn) even when delta is constant.

Název v anglickém jazyce

On the satisfiability of quantum circuits of small treewidth

Popis výsledku anglicky

It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time ... a classical assignment ... that maximizes the acceptance probability of C up to a delta additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)... For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t = O(logn) even when delta is constant.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theory of Computing Systems

ISSN

1432-4350

e-ISSN

—

Svazek periodika

61

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

656-688

Kód UT WoS článku

000405315000016

EID výsledku v databázi Scopus

2-s2.0-84996910310