Superposition as memory: unlocking quantum automatic complexity

DOI10.1007/978-3-319-58187-3_12MaRDI QIDQ2400959zbMATH OpenOpenAlexFDO

Publication date 31 August 2017

Full work available at URL https://arxiv.org/abs/1703.04878

automatic complexity finite automata quantum automata security

Quantum algorithms and complexity in the theory of computing (68Q12) Formal languages and automata (68Q45)

Abstract: Imagine a lock with two states, "locked" and "unlocked", which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e.,

0^{n} 1^{n}

where

n = 2

. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states "locked" and "unlocked", where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan--Schur lemma that a similar lock is not possible for

n = 60

. We define the semi-classical quantum automatic complexity

Q_{s} (x)

of a word

x

as the infimum in lexicographic order of those pairs of nonnegative integers

(n, q)

such that there is a subgroup

G

of the projective unitary group PU

(n)

with

| G | l e q

and with

U_{0}, U_{1} i n G

such that, in terms of a standard basis

e_{k}

and with

U_{z} = p r o d_{k} U_{z (k)}

, we have

U_{x} e_{1} = e_{2}

and

U_{y} e_{1} e e_{2}

for all

y e x

with

| y | = | x |

. We show that

Q_{s}

is unbounded and not constant for strings of a given length. In particular, [ Q_{s}(0^21^2)le (2,12) < (3,1) le Q_{s}(0^{60}1^{60}) ] and

Q_{s} (0^{120}) l e (2, 121)

.

Recommendations

This page was built for publication: Superposition as memory: unlocking quantum automatic complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400959)