2020/10/07 by Kai Sun, Zijian Zhang, Sun, Kai +15
Computer Science · Engineering · Physics and Astronomy · #FOS: Physical sciences #Molecular Junctions and Nanostructures #Optics (physics.optics) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum and electron transport phenomena
paper · pdf · doi:10.48550/arxiv.2010.03461
openalex publication_date 2020/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Decision problems are the problems whose answer is either YES or NO. As the quantum analogue of NP (nondeterministic polynomial time), the class 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 QMA. Previous works on the verification of GNM required a quantum circuit with O(n5) 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.