机构名称：
¥ 1.0
随机步行（或马尔可夫链）是随机模型，在理论计算机科学中广泛使用。从经典上讲，通过图定义随机步行，其中节点是过程的可能状态，边缘代表可能的过渡。在每个步骤中，根据某些概率分布选择了当前状态的外向边缘，并达到相应的状态。马尔可夫链的理论是对许多算法的分析的基础：一个显着的例子是Schönin的算法，这是最知名的令人满意的经典算法之一（SAT）问题[1]。马尔可夫连锁店的一个重要属性是所谓的打击时间，它量化了我们需要执行的步行数量（预期），以达到或达到一些固定的目标状态，但给定一些初始条件。对打击时间的分析是搜索问题的强大工具[2,3,4,5]，因为这些数量通常与复杂性指标密切相关。作为一个例子，请考虑令人满意的问题：给定F（x），我们从某个分配x 0开始（例如，x 0 =（0，。。。，0）），在每个步骤中，我们选择一个变量以随机均匀地翻转。这可以正式化为在超立方体上的随机步行，并且给定F的分配x ∗，从x 0到x ∗的击中时间平均告诉我们要达到该分配所需的步骤数。一种运行Markov链的算法并在每个步骤检查当前状态是否满足F的时间复杂性与打击时间成正比。在过去的几十年中，几项研究工作致力于将随机步行的概念扩展到量子设置，目的是实现某些速度
一般量子马尔可夫过程的打击时间
主要关键词
相关文件推荐
