On the satisfiability of quantum circuits of small treewidth

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
On the satisfiability of quantum circuits of small treewidth
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)