Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth
78
0
0.0
(
0
)
Authors
Mateus de Oliveira Oliveira
Ask ChatGPT about the research
No Arabic abstract
We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $Omega(frac{n^{2}}{2^{O(rcdot t)}cdot log^4 n})$ gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nev{c}iporuks method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry.
rate research
Read More
It has been known for almost three decades that many $mathrm{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, $mathit{poly}(n)$ gates, and treewidth $t$, one can compute in time $(frac{n}{delta})^{exp(O(t))}$ a classical assignment $yin {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) < delta < 1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the same problem is $mathrm{NP}$-complete if $t=O(log n)$ even when $delta$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(log n)$, and a constant $delta<1/2$, it is $mathrm{QMA}$-complete to determine whether there exists a quantum state $mid!varphirangle in (mathbb{C}^d)^{otimes n}$ such that the acceptance probability of $Cmid!varphirangle$ is greater than $1-delta$, or whether for every such state $mid!varphirangle$, the acceptance probability of $Cmid!varphirangle$ is less than $delta$. As a consequence, under the widely believed assumption that $mathrm{QMA} eq mathrm{NP}$, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problems hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Omega(N^{1/5}/log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainiss adversary theorem.
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the circuits which take a matrix input are unchanged by a permutation applied simultaneously to the rows and columns of the matrix. Under such restrictions we have polynomial-size circuits for computing the determinant but no subexponential size circuits for the permanent. Here, we consider a more stringent symmetry requirement, namely that the circuits are unchanged by arbitrary even permutations applied separately to rows and columns, and prove an exponential lower bound even for circuits computing the determinant. The result requires substantial new machinery. We develop a general framework for proving lower bounds for symmetric circuits with restricted symmetries, based on a new support theorem and new two-player restricted bijection games. These are applied to the determinant problem with a novel construction of matrices that are bi-adjacency matrices of graphs based on the CFI construction. Our general framework opens the way to exploring a variety of symmetry restrictions and studying trade-offs between symmetry and other resources used by arithmetic circuits.
We prove that with high probability over the choice of a random graph $G$ from the ErdH{o}s-Renyi distribution $G(n,1/2)$, a natural $n^{O(varepsilon^2 log n)}$-time, degree $O(varepsilon^2 log n)$ sum-of-squares semidefinite program cannot refute the existence of a valid $k$-coloring of $G$ for $k = n^{1/2 +varepsilon}$. Our result implies that the refutation guarantee of the basic semidefinite program (a close variant of the Lovasz theta function) cannot be appreciably improved by a natural $o(log n)$-degree sum-of-squares strengthening, and this is tight up to a $n^{o(1)}$ slack in $k$. To the best of our knowledge, this is the first lower bound for coloring $G(n,1/2)$ for even a single round strengthening of the basic SDP in any SDP hierarchy. Our proof relies on a new variant of instance-preserving non-pointwise complete reduction within SoS from coloring a graph to finding large independent sets in it. Our proof is (perhaps surprisingly) short, simple and does not require complicated spectral norm bounds on random matrices with dependent entries that have been otherwise necessary in the proofs of many similar results [BHK+16, HKP+17, KB19, GJJ+20, MRX20]. Our result formally holds for a constraint system where vertices are allowed to belong to multiple color classes; we leave the extension to the formally stronger formulation of coloring, where vertices must belong to unique colors classes, as an outstanding open problem.
We prove that with high probability over the choice of a random graph $G$ from the ErdH{o}s-Renyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/log n)^{1/2}}$ for some constant $c>0$. This yields a nearly tight $n^{1/2 - o(1)}$ bound on the value of this program for any degree $d = o(log n)$. Moreover we introduce a new framework that we call emph{pseudo-calibration} to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
