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 ≤ q and with U_0, U_1 ∈ G such that, in terms of a standard basis {e_k} and with U_z = Ⅱ_k U_z(k), we have U_xe_1 = e_2. and U_ye_1 ≠ e_2 for all y ≠ 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) ≤ (2,12) < (3,1) ≤ Q_s(0~(60)1~(60)) and Q_s (0~(120))≤(2,121).
展开▼
机译：我们将单词x的半经典量子自动复杂度Q_s（x）定义为这对非负整数（n，q）的字典顺序的最小值，这样就存在射影ary群PU（n）的子组G \\ G \≤q且U_0且U_1∈G，这样，就标准基数{e_k}而言，并且U_z =Ⅱ_kU_z（k），我们的U_xe_1 = e_2。对于所有y≠x的U_ye_1≠e_2，其中\ y \ = | x |。我们表明，对于给定长度的字符串，Q_s是无界的并且不是恒定的。特别是Q_s（0〜21〜2）≤（2,12）<（3,1）≤Q_s（0〜（60）1〜（60））和Q_s（0〜（120））≤（2,121） 。
展开▼
