The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem

• URL: http://arxiv.org/abs/2003.09879v2
• Date: Tue, 28 Apr 2020 17:18:59 GMT
• Title: The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem
• Authors: Zachary Remscrim (MIT)
• Abstract summary: Two-way finite automaton with quantum and classical states (2QCFA) is a model of quantum computation whose quantum part is extremely limited. We show that 2QCFA can recognize the language $L_eq=am bm :m mathbbN$ in expected time and the language $L_pal=w in a,b*:w CFA CFA is a palindrome$ in expected exponential time.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with bounded error, the language $L_{eq}=\{a^m b^m :m \in \mathbb{N}\}$ in expected polynomial time and the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ in expected exponential time. We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of many groups. In particular 2QCFA, with a single qubit and algebraic number transition amplitudes, can recognize, with bounded error, the word problem of any finitely generated virtually abelian group in expected polynomial time, as well as the word problems of a large class of linear groups in expected exponential time. This latter class (properly) includes all groups with context-free word problem. We also exhibit results for 2QCFA with any constant number of qubits. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that $L_{eq}$ can be recognized by a 2QCFA with better parameters. As a further corollary, we show that 2QCFA can recognize certain non-context-free languages in expected polynomial time. In a companion paper, we prove matching lower bounds, thereby showing that the class of languages recognizable with bounded error by a 2QCFA in expected $\mathit{subexponential}$ time is properly contained in the class of languages recognizable with bounded error by a 2QCFA in expected $\mathit{exponential}$ time.

Related papers

• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  We generalize quantum-classical PCPs to allow for $q$ quantum queries to a classical proof. Surprisingly, this shows that we can amplify the promise gap from inverse to constant for constant query quantum-classicals. Even though we can achieve promise gap, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $mathsfQCMA$.
  arXiv  Detail & Related papers  (2024-11-01T18:00:56Z)
• 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)
• The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
  We show that the entangled quantum quantum hierarchy $mathsfQEPH$ collapses to its second level. We also show that only quantum superposition (not classical probability) increases the computational power of these hierarchies.
  arXiv  Detail & Related papers  (2024-01-02T22:25:56Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• MIP*=RE [9.42581332803306]
  We show that the class MIP* of languages can be decided by a classical verifier interacting with multiple quantum provers sharing entanglement. We provide a refutation of Connes' theory of von Neumann algebras.
  arXiv  Detail & Related papers  (2020-01-13T16:32:40Z)
• Quantum Büchi Automata [4.998632546280976]
  We introduce the classes of $omega$-languages recognized by QBAs in probable, almost sure, strict and non-strict threshold semantics. We show that there are surprisingly only at most four substantially different classes of $omega$-languages recognized by QBAs (out of uncountably infinite) The relationship between classical $omega$-languages and QBAs is clarified using our pumping lemmas.
  arXiv  Detail & Related papers  (2018-04-24T12:23:49Z)

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.