10.decembrī notiks Mateus de Oliveira Oliveira vadīts seminārs

Plašāka informācija par semināru:

Title: On the Satisfiability of Quantum Circuits of Small Treewidth Author: Mateus de Oliveira Oliveira Abstract: It has been known since long time 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 \frac{n}{\delta})^{\exp(O(t))} a classical witness y\in \{0,1\}^n 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) \leq  \delta < 1. For unrestricted values of t this problem is known to be hard for the complexity class QCMA, a quantum generalization of NP. In contrast, we show that the same problem is already NP-hard if t=O(\log n) even when \delta is constant. Finally, we show that for t=O(\log n) and constant \delta, it is QMA-hard to find a quantum witness \ket{\varphi} that maximizes the acceptance probability of a quantum circuit of treewidth t up to a \delta additive factor.