notesum.ai

Published at December 3

Unconditional proofs of quantumness between small-space machines

cs.CC

cs.FL

quant-ph

Released Date: December 3, 2024

Authors: A. C. Cem Say¹, M. Utkan Gezer¹

Aff.: ¹Boğaziçi University

Arxiv: http://arxiv.org/pdf/2412.02662v1

Language	Description
$\mathtt{PAL}$	$\Set{w}{w=w^{R}}$
$\mathtt{TWIN}$	$\Set{w\#w}{w\in\Set{a,b}^{*}}$
$\mathtt{MULT}$	$\Set{x\#y\#z}{x,y,z\text{ are natural numbers in binary notation and }x\cdot y% =z}$
$\mathtt{SQUARE}$	$\Set{a^{i}b^{i^{2}}}{i>0}$
$\mathtt{POWER}$	$\Set{a^{i}b^{2^{i}}}{i>0}$
any “polynomial language”	A polynomial language [28] is defined as $\Set{a_{1}^{n_{1}}\dotsm a_{k}^{n_{k}}b_{1}^{p_{1}(n_{1},\dotsc,n_{k})}\dotsm b% _{r}^{p_{r}(n_{1},\dotsc,n_{k})}}{p_{i}(n_{1},\dotsc,n_{k})\geq 0},$ where $a_{1},\dotsc,a_{k},b_{1},\dotsc,b_{r}$ are distinct symbols, and each $p_{i}$ is a polynomial with integer coefficients.
$\mathtt{W_{G}}$	the word problem [31] for $G$ , where $G$ is any finitely generated virtually free group