Towards a universal gateset for $\mathsf{QMA}_1$

• URL: http://arxiv.org/abs/2411.02681v1
• Date: Mon, 04 Nov 2024 23:39:27 GMT
• Title: Towards a universal gateset for $\mathsf{QMA}_1$
• Authors: Dorian Rudolph,
• Abstract summary: We prove that for all gatesets in the cyclotomic field $mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$, $G_2k$ is universal for all gatesets in $mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$. We also prove that the Gapped Clique Homology problem defined by King
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: $\mathsf{QMA}_1$ is $\mathsf{QMA}$ with perfect completeness, i.e., the prover must accept with a probability of exactly $1$ in the YES-case. Whether $\mathsf{QMA}_1$ and $\mathsf{QMA}$ are equal is still a major open problem. It is not even known whether $\mathsf{QMA}_1$ has a universal gateset; Solovay-Kitaev does not apply due to perfect completeness. Hence, we do not generally know whether $\mathsf{QMA}_1^G=\mathsf{QMA}_1^{G'}$ (superscript denoting gateset), given two universal gatesets $G,G'$. In this paper, we make progress towards the gateset question by proving that for all $k\in\mathbb N$, the gateset $G_{2^k}$ (Amy et al., RC 2024) is universal for all gatesets in the cyclotomic field $\mathbb{Q}(\zeta_{2^k}),\zeta_{2^k}=e^{2\pi i/2^k}$, i.e. $\mathsf{QMA}_1^G\subseteq\mathsf{QMA}_1^{G_{2^k}}$ for all gatesets $G$ in $\mathbb{Q}(\zeta_{2^k})$. For $\mathsf{BQP}_1$, we can even show that $G_2$ suffices for all $2^k$-th cyclotomic fields. We exhibit complete problems for all $\mathsf{QMA}_1^{G_{2^k}}$: Quantum $l$-SAT in $\mathbb{Q}(\zeta_{2^k})$ is complete for $\mathsf{QMA}_1^{G_{2^k}}$ for all $l\ge4$, and $l=3$ if $k\ge3$, where quantum $l$-SAT is the problem of deciding whether a set of $l$-local Hamiltonians has a common ground state. Additionally, we give the first $\mathsf{QMA}_1$-complete $2$-local Hamiltonian problem: It is $\mathsf{QMA}_1^{G_{2^k}}$-complete (for $k\ge3$) to decide whether a given $2$-local Hamiltonian $H$ in $\mathbb{Q}(\zeta_{2^k})$ has a nonempty nullspace. Our techniques also extend to sparse Hamiltonians, and so we can prove the first $\mathsf{QMA}_1(2)$-complete (i.e. $\mathsf{QMA}_1$ with two unentangled provers) Hamiltonian problem. Finally, we prove that the Gapped Clique Homology problem defined by King and Kohler (FOCS 2024) is $\mathsf{QMA}_1^{G_2}$-complete, and the Clique Homology problem without promise gap is PSPACE-complete.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  We show $mathsfQ(f_mathsfsab)$, the quantum query complexity of $f_mathsfsab$. We show that when $f$ is the Indexing function, $mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$, ruling out the possibility that $mathsfQ(f_mathsfsab)=Theta(sqrtmathsf
  arXiv  Detail & Related papers  (2024-08-22T17:57:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates [0.0]
  For a random set $mathcalS subset U(d)$ of quantum gates we provide bounds on the probability that $mathcalS$ forms a $delta$-approximate $t$-design. We show that for $mathcalS$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbbPleft(delta geq x right)leq 2D_t
  arXiv  Detail & Related papers  (2022-02-10T23:44:09Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• How to check universality of quantum gates? [0.0]
  Our first criterion states that $mathcalSsubset G_d:=U(d)$ is universal if and only if $mathcalS$ forms a $delta$-approximate $t(d)$-design. Our second universality criterion says that $mathcalSsubset G_d$ is universal if and only if the centralizer of $mathcalSt(d),t(d)=Uotimes t(d)otimes t(d)|U
  arXiv  Detail & Related papers  (2021-11-06T11:58:32Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits. We show that both variants of $mathsfStoqMA$ that without any ancillary random bit and with perfect soundness are contained in $mathsfNP$. Our results make a step towards collapsing the hierarchy $mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06], in which all classes are contained in $
  arXiv  Detail & Related papers  (2020-11-11T12:30:42Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.