Exponentiallymoreconcisequantumrecognitionofnon-RMMregularlanguages资源-CSDN文库

79 浏览量 2021-02-20 23:50:58 上传评论收藏 609KB PDF 举报

标题和描述中提到的论文内容，主要讨论了量子有限自动机（Quantum Finite Automata，简称QFA）的一个新模型——即带有经典状态的一维量子有限自动机（one-way Quantum Finite Automaton with Classical States，简称1QFAC）。研究发现，1QFAC能够精确识别所有的正则语言，并且在有界错误的情况下，这种模型的量子自动机对正则语言的识别比确定性有限自动机（Deterministic Finite Automata，简称DFA）最多是指数级的简洁。具体来说，论文证明了1QFAC对于那些不能被测量一次（RMO），测量多次（RMM）以及多字母1QFA识别的正则语言家族，存在一个指数级的上界。同时，论文还提出了一种多项式时间算法来判断任意两个1QFAC是否等价，并且证明了1QFAC的状态最小化问题是可判定的，并在EXPSPACE复杂性类别中。在关键词部分，我们可以看到这篇论文所涉猎的领域包括了量子有限自动机（QFA）、等价性（Equivalence）、正则语言（Regular languages）、确定性有限自动机（Deterministic finite automata）、可判定性（Decidability）以及状态复杂性（State complexity）。以下是根据给定文件信息，详细说明的知识点： 1. **量子有限自动机（QFA）**：量子有限自动机是一种理论计算模型，其特点在于有限的存储空间和有限维的状态空间。它是经典有限自动机的一种量子版本，后者作为经典计算模型中的有限内存的自然代表。QFA的研究动机之一是为了探讨经典和量子计算复杂度类之间的关系。 2. **带有经典状态的量子有限自动机（1QFAC）**：1QFAC是本文提出的新型计算模型，它是一维量子有限自动机的扩展，加入经典状态概念。这种模型能够精确识别所有的正则语言，并且在识别过程中比DFA更为简洁。 3. **正则语言（Regular languages）**：正则语言是形式语言理论中的一个基础概念，包含所有可以被有限自动机所识别的语言。1QFAC模型能够识别所有的正则语言，说明了量子自动机在处理这类问题上的潜力。 4. **指数级简洁性**：在本论文中，研究者证明了在有界错误的条件下，对于不是由RMO、RMM和多字母1QFA识别的正则语言家族，1QFAC的简洁性是指数级的。这一发现表明，对于某些特定类型的语言，量子自动机具有超越传统自动机的潜力。 5. **等价性问题**：研究者提出了一种多项式时间算法来判定任意两个1QFAC是否等价，这有助于进一步理解该模型在理论上的性质。 6. **状态最小化问题**：对于1QFAC模型，状态最小化问题已被证明是可判定的，并且其解的复杂度位于EXPSPACE复杂性类别内。这意味着对于这类问题，尽管计算资源的需求可能非常高，但存在算法能在理论上给出答案。 7. **计算模型的复杂度分析**：在讨论QFA、1QFAC与DFA的性能比较时，复杂度分析是核心议题。理解不同计算模型在处理相同问题时的资源使用情况和效率差异，是理论计算机科学中的一个重要方面。总体而言，这篇论文提供了一个新的视角来研究量子计算模型在处理特定问题集时的性能优势。通过比较量子和经典计算模型，研究者不仅揭示了量子计算在理论上可能达到的极限，还为未来可能的实际应用奠定了基础。这些发现对于深入理解量子计算的潜力以及对于计算机科学的理论研究和实际应用都具有重要意义。

资源推荐

资源详情

资源评论

Journal of Computer and System Sciences 81 (2015) 359–375

Contents lists available at ScienceDirect

Journal of Computer and System Sciences

www.elsevier.com/locate/jcss

Exponentially more concise quantum recognition of non-RMM

regular languages

Daowen Qiu

a,b,∗

, Lvzhou Li

, Paulo Mateus

, Amilcar Sernadas

Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China

SQIG–Instituto de Telecomunicações, Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais

1049-001, Lisbon, Portugal

a r t i c l e i n f o a b s t r a c t

Article history:

Received

2 June 2012

Accepted

4 June 2014

Available

online 27 June 2014

Keywords:

Quantum

ﬁnite automata

Equivalence

Regular

languages

Deterministic

ﬁnite automata

Decidability

State

complexity

We introduce a new computing model of one-way quantum ﬁnite automata (1QFA), namely,

one-way quantum ﬁnite automata together with classical states (1QFAC). We show that the

set of languages accepted by 1QFAC with bounded error consists precisely of all regular

languages. In particular, we prove that 1QFAC are at most exponentially more concise than

DFA by giving a lower bound, and we also show that this bound is tight for families of

regular languages that are not recognized by measure-once (RMO), measure-many (RMM)

and multi-letter 1QFA. Then, we give a polynomial-time algorithm for determining whether

any two 1QFAC are equivalent. In addition, we show that the state minimization of 1QFAC

is decidable within EXPSPACE.

1. Introduction

Quantum ﬁnite automata (QFA) can be thought of as a theoretical model of quantum computers in which the memory is

ﬁnite and described by a ﬁnite-dimensional state space [1], as ﬁnite automata are a natural model for classical computing

with ﬁnite memory [21]. As mentioned in [20], one of the motivations to study QFA is to provide some ideas to investigate

the relation of classical and quantum computational complexity classes. This kind of theoretical models was ﬁrstly studied

by Moore and Crutchﬁeld [28], Kondacs and Watrous [24], and then Ambainis and Freivalds [2], Brodsky and Pippenger

[13], and other authors (e.g., the references in [37]). The study of QFA is mainly divided into two ways: one is one-way

quantum ﬁnite automata (1QFA) whose tape heads move one cell only to right at each evolution, and the other two-way

quantum ﬁnite automata (2QFA), in which the tape heads are allowed to move towards right or left, or to be stationary.

According to the measurement times in a computation, 1QFA have two types: measure-once 1QFA (MO-1QFA) initiated by

Moore and Crutchﬁeld [28] and measure-many 1QFA (MM-1QFA) studied ﬁrst by Kondacs and Watrous [24]. In MO-1QFA,

there is only a measurement for computing each input string, performing after reading the last symbol; in contrast, in

MM-1QFA, measurement is performed after reading each symbol, instead of only the last symbol. Notably, QFA have been

applied to quantum interactive proof systems [32].

MM-1QFA

can accept more languages than MO-1QFA with bounded error [2], but both of them accept proper subsets

of regular languages [13,11]. Another model of 1QFA with a measurement is called multi-letter 1QFA, proposed in [10].

In multi-letter 1QFA, there are multi-reading heads. Roughly speaking, a k-letter 1QFA is not limited to seeing only one,

the just-incoming input letter, but can see several earlier received letters as well. Though multi-letter 1QFA can accept

Corresponding author at: Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China.

E-mail

addresses: issqdw@mail.sysu.edu.cn (D. Qiu), pmat@math.ist.utl.pt (P. Mateus), acs@math.ist.utl.pt (A. Sernadas).

http://dx.doi.org/10.1016/j.jcss.2014.06.008

0022-0000/

360 D. Qiu et al. / Journal of Computer and System Sciences 81 (2015) 359–375

some regular languages not acceptable by MM-1QFA, they still accept a proper subset of regular languages. Nevertheless,

as Ambainis et al. [3] mentioned, suﬃcient general 1QFA can indeed accept the same set of languages as DFA, for example,

1QFA with control languages (1QFACL, for short) proposed in [11] accept all regular languages (and only regular languages)

[11,30]. However, the measurements in 1QFACL differ from those in MM-1QFA proposed in [24].

Paschen

[33] presented a different 1QFA by adding some ancilla qubits to avoid the restriction of unitarity, and this model

is called an ancilla 1QFA. Indeed, in ancilla 1QFA, the transition function corresponding to every input symbol is described

by an isometry mapping, instead of a unitary operator. In [33], it was proved that ancilla 1QFA can recognize any regular

language with certainty. With the idea in Bennett [6], Ciamarra [15] proposed another model of 1QFA whose computational

power was shown to be at least equal to that of classical automata. For convenience, we call the 1QFA deﬁned in [15] as

Ciamarra 1QFA named after the author. In fact, the internal state of a Ciamarra 1QFA evolves by a trace-preserving quantum

operation. In addition, in [27] it was proved that both ancilla 1QFA and Ciamarra 1QFA recognize only regular languages.

Recently, it was proved that MO-1QFA and MM-1QFA with mixed states and trace-preserving quantum operations, instead

of unitary operators, as the evolutions of states, can accept all and only regular languages [27].

These

1QFA indicated above can accept all regular languages, but their architectures are much more complicated than

MO-1QFA, and more diﬃcult to be implemented physically with present technology. Hence, proposing and exploring prac-

tical

models of quantum computation is an important research problem and provide relevant insights to study physical

models of quantum computers. Indeed, motivated by the implementations of quantum computers using nucleo-magnetic

resonance (NMR), Ambainis et al. [1] proposed another model of 1QFA, namely, Latvian 1QFA (L-1QFA, for short). In L-1QFA,

measurement is also allowed after reading each input symbol, but they accept a proper subset of regular languages [1].

Notably, the languages recognized with unbounded error by QFA have been discussed in [46,47].

Though

ancilla 1QFA and Ciamarra 1QFA can accept all regular languages, their evolution operators of states are general

quantum operations instead of unitary operators. 1QFA with pure states and unitary evolutions usually have less recognition

power than deterministic ﬁnite automata (DFA) due to the unitarity (reversibility) of quantum physics and the ﬁnite memory

of ﬁnite automata. 1QFACL can accept all regular languages but their measurement is quite complicated. However, one would

expect a quantum variant to exceed (or at least to be not weaker than) the corresponding classical computing model, and

such quantum computing models are practical and feasible as well. For this reason, we think that a quantum computer

should inherit the characteristics of classical computers but further advance classical component by employing quantum

mechanics principle.

Motivated

by this idea, we propose a new model of quantum automata including a classical component, i.e., we re-

formulate

the deﬁnition of this new model of MO-1QFA, namely, 1QFA together with classical states (1QFAC, for short), and

in particular, we investigate some of the basic properties of this new model. As MO-1QFA [28,13], 1QFAC execute only a

measurement for computing each input string, following the last symbol scanned. In this new model, we preserve the com-

ponent

of DFA that is used to control the choice of unitary transformation for scanning each input symbol. We now describe

roughly a 1QFAC A computing an input string, delaying the details until Section 2.

start up, automaton A is in an initial classical state and in an initial quantum state. By reading the ﬁrst input symbol,

the classical transformation results in a new classical state as current state, and, the initial classical state together with

current input symbol assigns a unitary transformation to process the initial quantum state, leading to a new quantum

state as current state. Afterwards, the machine reads the next input symbol, and similar to the above process, its classical

state will be updated by reading the current input symbol and, at the same time, with the current classical state and

input symbol, a new unitary transformation is assigned to execute the current quantum state. Subsequently, it continues to

operate for the next step, until the last input symbol has been scanned. According to the last classical state, a measurement

is assigned to perform on the ﬁnal quantum state, producing a result of accepting or rejecting the input string.

Therefore,

a 1QFAC performs only one measurement for computing each input string, doing so after reading the last

symbol. However, the measurement is chosen according to the last classical state reached after scanning the input string.

Thus, when a 1QFAC has only one classical state, it reduces to an MO-1QFA [28,13]. On the one hand, 1QFAC model develops

MO-1QFA by adding DFA’s component, and on the other hand, 1QFAC advance DFA by employing the fundamentals of

quantum mechanics.

want to stress that 1QFAC are not the one-way version of two-way ﬁnite automata with quantum and classical states

(2QCFA

for short) proposed by Ambainis and Watrous [4], and this version has been preliminarily considered in [49]. One of

the differences is that, according to the deﬁnition of 2QCFA [4], in the one-way version of 2QCFA, after the tape head reads

an input symbol, either a measurement or a unitary transformation is performed, while in 1QFAC there is no intermediate

measurement, and a single measurement is performed only after scanning the input string.

Though

1QFAC make only one measurement for computing each input string and the evolutions of states are unitary

instead of general operations, the set of languages accepted by 1QFAC (with no error) consists precisely of all regular

languages. As we know, the set of languages accepted by 1QFACL is constituted by all regular languages [30], but 1QFACL

need measurement after reading each input symbol and the measurement is not only restricted to accepting, rejecting,

and non-halting, but also other results related to the control language attached to the machine. Therefore, the computing

process of a 1QFACL is usually much more complicated than that of a 1QFAC. On the other hand, measuring may lead to

more errors for the machine.

prove exponential size advantages for a class of automata over DFA is a diﬃcult problem, especially if the class of

automata is such that they accept only all regular languages. Since 1QFA do not have more power than DFA in terms of

D. Qiu et al. / Journal of Computer and System Sciences 81 (2015) 359–375 361

accepting languages, it is more important to discover the space-eﬃciency of 1QFA compared with other one-way automata.

The ﬁrst important result is by Ambainis and Freivalds [2], who proved that MO-1QFA need exponentially less number of

states than DFA for accepting some languages. (Recently, Ambainis and Nahimovs [3] have further improved this result.) For

probabilistic ﬁnite automata, it is also worth recalling that the ﬁrst advantages of probabilistic ﬁnite automata were proved

by Rabin [40], but the exponential advantages were proved by Freivalds [17].

[12,29–31], Bertoni, Mereghetti, and Palano further proved that MO-1QFA have space-eﬃcient advantage over DFA for

accepting some languages. As mentioned before, MO-1QFA with mixed states and general quantum operations can accept

all regular languages. Indeed, Freivalds et al. [16] proved that MO-1QFA with mixed states are super-exponentially more

concise than MO-1QFA with pure states.

should be stressed that 1QFAC can accept regular languages with exponentially less states than the corresponding DFA

[21], and for which there is no MO-1QFA [28], nor MM-1QFA [24], nor multi-letter 1QFA [10] that can accept them with

bounded error. Hence, in a way, 1QFAC can be thought of as a more practical model of QFA, showing better state complexity

than DFA due to its quantum computing component, and stronger recognition power of languages than MO-1QFA, MM-1QFA,

and multi-letter 1QFA. Furthermore, for accepting the same regular language, we will show that 1QFAC have better state

complexity than 1QFACL.

1.1. Original contributions

The main technical contributions of the paper contain ﬁve aspects. In Section 2, after reviewing some existing 1QFA

models, we deﬁne 1QFAC formally and then prove that the set of languages accepted by 1QFAC with bounded error includes

all regular languages.

Then,

in Section 3, we study the state complexity of 1QFAC. We prove that if L is accepted by a 1QFAC M with bounded

error, then L is regular and kn = Ω(log m) where k and n denote numbers of classical states and quantum basis states of M,

respectively, and m is the state number of the minimal DFA accepting L. Then, we verify this bound is indeed tight, since

we further show that, for any prime m ≥ 2, there exists a regular language L

whose minimal DFA needs m + 1states and

neither MO-1QFA nor MM-1QFA can accept L

, but there exists a 1QFAC accepting L

with only two classical states and

O (log(m)) quantum basis states. In addition, we show that, for any m ≥ 2, and any input string z, there exists a regular

language L

(m) that can not be accepted by any multi-letter 1QFA or MO-1QFA, but there exists a 1QFAC A

accepting it

with only 2 classical states and O (log(m)) quantum basis states. In contrast, the minimal DFA accepting L

(m) has (|z| +1)m

states,

where |z| denotes the length of z.

Section 4, we study the equivalence problem of 1QFAC. Any two 1QFAC A

and A

over the same input alphabet Σ

are equivalent (resp. k-equivalent) iff their probabilities for accepting any input string (resp. length not more than k) are

equal. We reformulate any given 1QFAC with a bilinear computing machine. According to [40,34,44], it follows that 1QFAC

and A

over the same input alphabet Σ are equivalent if and only if they are (k

)

+ (k

)

− 1-equivalent, and

furthermore there exists a polynomial-time O ([(k

)

+ (k

)

]

) algorithm for determining their equivalence, where k

and k

are the numbers of classical states of A

and A

, as well as n

and n

are the numbers of quantum basis states of

and A

, respectively.

Finally,

in Section 5, we show that minimization of a 1QFAC is decidable in EXPSPACE. To this end, we capitalize on the

results of Section 4 and on Renegard’s algorithm [41] for sampling semialgebraic sets.

general, notation used in this paper will be explained whenever new symbols appear. A language L over alphabet Σ

is accepted by a computing model with bounded error if there exist λ > 0 and  > 0such that the accepting probability for

x ∈ L is at least λ + and the accepting probability for x /∈ L is at most λ −. In this paper, we always consider the accepting

scheme of machines to be bounded error unless we emphasize otherwise. Throughout this paper, the notation . denotes

the Euclid norm of a vector.

2. One-way quantum ﬁnite automata together with classical states

In this section, we introduce the deﬁnition of 1QFAC and then prove its recognition power of languages. For the sake of

readability, we ﬁrst recall the deﬁnitions of MO-1QFA, MM-1QFA, multi-letter 1QFA, and 1QFACL.

2.1. Review of other one-way quantum ﬁnite automata

An MO-1QFA is deﬁned as a quintuple A = (Q , Σ, |ψ

, {U (σ )}

σ ∈Σ

, Q

acc

), where Q is a set of ﬁnite states, |ψ

 is the

initial state that is a superposition of the states in Q , Σ is a ﬁnite input alphabet, U (σ ) is a unitary matrix for each σ ∈Σ,

and Q

acc

⊆ Q is the set of accepting states.

usual, we identify Q with an orthonormal base of a complex Euclidean space and every state q ∈ Q is identi-

ﬁed

with a basis vector, denoted by Dirac symbol |q (a column vector), and q| is the conjugate transpose of |q. We

describe the computing process for any given input string x = σ

···σ

∈ Σ

∗

. At the beginning the machine A is

in the initial state |ψ

, and upon reading σ

, the transformation U (σ

) acts on |ψ

. After that, U (σ

)|ψ

 becomes

the current state and the machine reads σ

. The process continues until the machine has read σ

ending in the state

剩余16页未读，继续阅读

评论收藏

内容反馈

weixin_38640443

粉丝: 10
资源: 885

Exponentially more concise quantum recognition of non-RMM regula...

最新资源

Exponentially more concise quantum recognition of non-RMM regula...

自适应模拟退火算法源码

基于单片机的IC卡读写器设计

vs 2005 10款插件

2020_ICM_Problem_E.pdf

Apache Oozie Essentials(PACKT,2015)

Java Crash Course [2016]

张量网络 part 1

Length enhancement of thermoelectric effects in DNA duplex chains dueto quantum interferences

Python: The Ultimate Python Quickstart Guide - From Beginner To Expert [2016]

Optimal multi-level thresholding using a two-stage Otsu optimization approach

Android 6 for Programmers, AN APP-DRIVEN APPROACH THIRD EDITION (pdf)

Enterprise Digitization Patterns

用户画像推荐系统springboot设计和实现 计算机专业.pdf

Greedy Layer-Wise Training

SIGMOD 2009 全部论文（1）

TI Vlib 用户手册

英文原版-What To Do When Machines Do Everything 1st Edition

Neural Networks for Applied Sciences and Engineering

Cloud and Fog Computing in 5G Mobile Networks-IET(2017).pdf

Plasmonics : Fundamentals and Applications

Consensus of Discrete-time Multi-agent Systems with Decaying Multiplicative Uncertainties

cascade r-cnn paper

A Guide to Physics Problems Part 1

A taxonomy and survey on Green Data Center Networks

Scaling Big Data with Hadoop and Solr

最新资源

用户画像推荐系统springboot设计和实现计算机专业.pdf