Verification of Group Non-membership by Shallow Quantum Circuits

• URL: http://arxiv.org/abs/2010.03461v1
• Date: Wed, 7 Oct 2020 14:53:15 GMT
• Title: Verification of Group Non-membership by Shallow Quantum Circuits
• Abstract summary: The problem of deciding the group non-membership (GNM) of a group element is known to be in $mathsfQMA$. We propose an efficient way to verify GNM problems, reducing the circuit depth to $O(1)$ and the number of qubits by half.
• Score: 6.611344035597144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision problems are the problems whose answer is either YES or NO. As the quantum analogue of $\mathsf{NP}$ (nondeterministic polynomial time), the class $\mathsf{QMA}$ (quantum Merlin-Arthur) contains the decision problems whose YES instance can be verified efficiently with a quantum computer. The problem of deciding the group non-membership (GNM) of a group element is known to be in $\mathsf{QMA}$. Previous works on the verification of GNM required a quantum circuit with $O(n^5)$ group oracle calls. Here we propose an efficient way to verify GNM problems, reducing the circuit depth to $O(1)$ and the number of qubits by half. We further experimentally demonstrate the scheme, in which two-element subgroups in a four-element group are employed for the verification task. A significant completeness-soundness gap is observed in the experiment.

Related papers

• Quantum state isomorphism problems for groups [41.49556721904551]
  We study the computational complexity of quantum state isomorphism problems under group actions.<n>For pure-state version, we show that the problem is BQP-hard for all nontrivial groups.<n>For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete.
  arXiv  Detail & Related papers  (2026-05-12T18:05:27Z)
• Two Problems on Quantum Computing in Finite Abelian Groups [0.0]
  In the context of finite Abelian groups two problems are presented and solved using quantum computing techniques.<n>The first is the well--known Hidden Subgroup Problem, originally solved by Simon.<n>The second is the Fully Balanced Image Problem, originally introduced by the authors.
  arXiv  Detail & Related papers  (2026-04-01T14:07:38Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Finding quantum partial assignments by search-to-decision reductions [0.0]
  We show that a quantum algorithm with access to a $mathsfQMA$ oracle can construct $mathsfQMA$ witnesses as quantum states. We prove that if one is not interested in the quantum witness as a quantum state but only in terms of its partial assignments, then there exists a classical-time algorithm with access to a $mathsfQMA$ oracle.
  arXiv  Detail & Related papers  (2024-08-07T18:00:00Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Alleviating the quantum Big-$M$ problem [0.237499051649312]
  Classically known as the "Big-$M$" problem, it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
  arXiv  Detail & Related papers  (2023-07-19T18:00:05Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
  We consider the problem of testing and learning quantum $k$-juntas. We give (a) a $widetildeO(sqrtk)$-query quantum algorithm that can distinguish quantum $k$-juntas from unitary matrices that are "far" from every quantum $k$-junta. We complement our upper bounds for testing quantum $k$-juntas and learning quantum $k$-juntas with near-matching lower bounds of $Omega(sqrtk)$ and $Omega(frac
  arXiv  Detail & Related papers  (2022-07-13T00:11:14Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• The Parameterized Complexity of Quantum Verification [7.7155343772895275]
  We show that for the problem of quantum circuit satisfiability, there exists an algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates. We derive new lower bounds on the $T$-count of circuit satisfiability instances and the $$-count of the $W$-state.
  arXiv  Detail & Related papers  (2022-02-16T14:53:42Z)
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans\"atze [13.651587339535961]
  We develop a framework for convolutional quantum circuits with SU$(d)$symmetry. We prove Harrow's statement on equivalence between $nameSU(d)$ and $S_n$ irrep bases.
  arXiv  Detail & Related papers  (2021-12-14T18:03:43Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)

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.