量子元胞自动机

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

此词条暂由彩云小译翻译，字数为1717字，未经人工整理和审校，带来阅读不便，请见谅。 此词条由舒寒初步翻译。

此词条由天天审校，未经专家审核，带来阅读不便，请见谅。

A quantum cellular automaton (QCA) is an abstract model of quantum computation, devised in analogy to conventional models of cellular automata introduced by John von Neumann. The same name may also refer to quantum dot cellular automata, which are a proposed physical implementation of "classical" cellular automata by exploiting quantum mechanical phenomena. QCA have attracted a lot of attention as a result of its extremely small feature size (at the molecular or even atomic scale) and its ultra·low power consumption, making it one candidate for replacing CMOS technology.

量子元胞自动机（QCA）是一种抽象的量子计算模型，它是根据约翰·冯·诺依曼（John von Neumann）提出的传统元胞自动机模型而设计的。这个名字也可以指量子点元胞自动机，它是利用量子力学现象而提出的 "经典 "元胞自动机的物理实现。QCA由于其极小的特征尺寸（在分子甚至原子尺度上）和超低的功耗而吸引了大量的关注，使其成为取代CMOS技术的候选者之一。

Usage of the term 应用

In the context of models of computation or of physical systems, quantum cellular automaton refers to the merger of elements of both (1) the study of cellular automata in conventional computer science and (2) the study of quantum information processing. In particular, the following are features of models of quantum cellular automata:

在计算模型或物理系统模型的背景下，量子元胞自动机指的是两种元素的合并: (1)传统计算机科学中的元胞自动机研究; (2)量子信息处理研究。特别地，以下是量子元胞自动机模型的特征:

在计算或物理系统的模型方面，量子元胞自动机指的是：传统计算机科学中的元胞自动机研究与量子信息处理研究两者元素的合并。特别是，以下是量子元胞自动机模型的特点。

  • The computation is considered to come about by parallel operation of multiple computing devices, or cells. The cells are usually taken to be identical, finite·dimensional quantum systems (e.g. each cell is a qubit).
  • 计算被认为是由多个计算设备或单元的平行操作而产生的。这些单元通常被认为是相同的、有限维的量子系统（例如，每个单元是一个量子比特）。
  • Each cell has a neighborhood of other cells. Altogether these form a network of cells, which is usually taken to be regular (e.g. the cells are arranged as a lattice with or without periodic boundary conditions).
  • 每个元胞都有一个其他元胞的邻居。这些元胞共同构成了一个元胞网络，通常被认为是有规律的（例如，元胞被排列成有或没有周期性边界条件的晶格）。
  • The evolution of all of the cells has a number of physics·like symmetries. Locality is one: the next state of a cell depends only on its current state and that of its neighbours. Homogeneity is another: the evolution acts the same everywhere, and is independent of time.
  • 所有元胞的演变都有一些类似物理学的对称性。局部性是其中之一：一个元胞的下一个状态只取决于它的当前状态和它的邻居的状态。同质性是另一种特性：演化在任何地方都是一样的，并且与时间无关。
  • The state space of the cells, and the operations performed on them, should be motivated by principles of quantum mechanics.
  • 元胞的状态空间以及对其进行的操作应以量子力学的原理为动力。

Another feature that is often considered important for a model of quantum cellular automata is that it should be universal for quantum computation (i.e. that it can efficiently simulate quantum Turing machines,[1][2] some arbitrary quantum circuit[3] or simply all other quantum cellular automata[4][5]).

另一个经常被认为对量子元胞自动机模型很重要的特征是，它对量子计算应该是通用的（即它可以有效地模拟量子图灵机、[1][2] 一些任意的量子电路[3] 或简单地模拟所有其他的量子元胞自动机[4][5]）。


Models which have been proposed recently impose further conditions, e.g. that quantum cellular automata should be reversible and/or locally unitary, and have an easily determined global transition function from the rule for updating individual cells.[2] Recent results show that these properties can be derived axiomatically, from the symmetries of the global evolution.[6][7][8]

新近提出的模型给出了进一步的条件，例如，量子元胞自动机应该是可逆的和/或局部单一的，并有一个容易确定的全局过渡函数，从而更新单个元胞的规则。[2] 最近的研究成果表明，这些特性可以从全局演化的对称性中以公理方式导出。[6][7][8]

Reversible quantum dot cellular automaton for addition and subtraction of two 8·qubit registers]]

用于两个8比特寄存器加减的可逆量子点元胞自动机（审校注：这里似乎缺了一张图片。）

Models 模型

Early proposals 早期发展

In 1982, Richard Feynman suggested an initial approach to quantizing a model of cellular automata.[9] In 1985, David Deutsch presented a formal development of the subject.[10] Later, Gerhard Grössing and Anton Zeilinger introduced the term "quantum cellular automata" to refer to a model they defined in 1988,[11] although their model had very little in common with the concepts developed by Deutsch and so has not been developed significantly as a model of computation.

1982年，理查德·费曼（Richard Feynman）提出了一个量子元胞自动机模型的初步方法。[9] 1985年，大卫·多伊奇（David Deutsch）推动了这一方法更进一步的发展。[10] 后来，格哈德·格罗辛（Gerhard Grössing）和安东·蔡林格（Anton Zeilinger）引入了 "量子元胞自动机 "这个名称来指代他们在1988年定义的模型，[11]尽管他们的模型与大卫·多伊奇（David Deutsch）所发展的量子元胞自动机几乎没有相同之处，所以没有作为计算模型而得到显著发展。

Models of universal quantum computation 通用量子计算的模型

The first formal model of quantum cellular automata to be researched in depth was that introduced by John Watrous.[1] This model was developed further by Wim van Dam,[12] as well as Christoph Dürr, Huong LêThanh, and Miklos Santha,[13][14] Jozef Gruska.[15] and Pablo Arrighi.[16] However it was later realised that this definition was too loose, in the sense that some instances of it allow superluminal signalling.[6][7] A second wave of models includes those of Susanne Richter and Reinhard Werner,[17] of Benjamin Schumacher and Reinhard Werner,[6] of Carlos Pérez·Delgado and Donny Cheung,[2] and of Pablo Arrighi, Vincent Nesme and Reinhard Werner.[7][8] These are all closely related, and do not suffer any such locality issue. In the end one can say that they all agree to picture quantum cellular automata as just some large quantum circuit, infinitely repeating across time and space.

第一个被深入研究的量子元胞自动机的正式模型是由约翰·沃特鲁斯（John Watrous）提出的。这个模型得到了维姆·范·达姆（Wim van Dam），[12] 克里斯托夫·迪尔（Christoph Dürr）, 黄乐清（音译，Huong LêThanh）, 米克罗斯·桑塔（Miklos Santha）, [13][14] 约瑟夫·格鲁什卡（Jozef Gruska）[13][14] [15]和巴勃罗·阿里吉（Pablo Arrighi）[15] [16] 的进一步发展。然而，后来人们意识到这样的模型定义过于宽松，因为它的一些实例允许超光速的存在。[6][7] 更进一步的模型由包括苏珊娜·里希特（Susanne Richter）和莱因哈德·维尔纳（Reinhard Werner）、[17] 本杰明·舒马赫（Benjamin Schumacher）和莱因哈德·维尔纳（Reinhard Werner）、[6] 卡洛斯·佩雷斯·德尔加多（Carlos Pérez·Delgado）和张多尼（音译，Donny Cheung）、[2] 以及巴勃罗·阿里吉（Pablo Arrighi）、文森特·内斯梅（Vincent Nesme）和莱因哈德·维尔纳（Reinhard Werner）等人提出。[7][8] 这些工作都是密切相关的，并不存在任何这样或是那样的地方性的问题。最后可以说，他们都支持把量子元胞自动机描绘成一些大的量子电路，从而在时间和空间上无限地重复。

Models of physical systems 物理系统的模型

Models of quantum cellular automata have been proposed by David Meyer,[18][19] Bruce Boghosian and Washington Taylor,[20] and Peter Love and Bruce Boghosian[21] as a means of simulating quantum lattice gases, motivated by the use of "classical" cellular automata to model classical physical phenomena such as gas dispersion.[22] Criteria determining when a quantum cellular automaton (QCA) can be described as quantum lattice gas automaton (QLGA) were given by Asif Shakeel and Peter Love.[23]

大卫·迈耶（David Meyer）、[18][19] 布鲁斯·博格森（Bruce Boghosian）[21] 和华盛顿·泰勒（Washington Taylor）[20] 以及彼得·洛夫（Peter Love）提出了量子元胞自动机的模型，作为模拟量子晶格气体的途径，其目的是使用 "经典"元胞自动机来模拟经典的物理现象，如气体的色散。[22] 阿西夫·沙克尔（Asif Shakeel）和彼得·洛夫（Peter Love）给出了确定量子元胞自动机（QCA）何时可以被描述为量子晶格气体自动机（QLGA）的标准。[23]

Quantum dot cellular automata 量子点元胞自动机

Category:Cellular automata

类别: 元胞自动机

A proposal for implementing classical cellular automata by systems designed with quantum dots has been proposed under the name "quantum cellular automata" by Doug Tougaw and Craig Lent, as a replacement for classical computation using CMOS technology. In order to better differentiate between this proposal and models of cellular automata which perform quantum computation, many authors working on this subject now refer to this as a quantum dot cellular automaton.

道格·图格（Doug Tougaw）和克雷格·兰特（Craig Lent）以 "量子元胞自动机 "为名，提出了一个用量子点设计的系统来实现经典元胞自动机的建议，作为使用CMOS技术的经典计算的替代。为了更好地区分这一建议和进行量子计算的元胞自动机模型，许多从事这一领域的研究人员现在将其称为量子点元胞自动机。


Category:Quantum information science

类别: 量子信息科学

Category:Richard Feynman

类别: 理查德 · 费曼


This page was moved from wikipedia:en:Quantum cellular automaton. Its edit history can be viewed at 量子元胞自动机/edithistory

  1. ↑ 1.0 1.1 1.2 {{citation 通常被认为对量子细胞自动机模型很重要的另一个特征是，它对于量子计算应该是通用的（即，它可以有效地模拟量子图灵机，某些任意量子电路或简单地所有其他量子细胞自动机）。 | last = Watrous | first = John | authorlink = John Watrous (computer scientist) | contribution = On one-dimensional quantum cellular automata Models which have been proposed recently impose further conditions, e.g. that quantum cellular automata should be reversible and/or locally unitary, and have an easily determined global transition function from the rule for updating individual cells. 最近提出的模型施加了进一步的条件，例如:量子细胞自动机应该是可逆的和（或）局部单一的，并且具有根据更新单个细胞的规则中容易确定的全局转换函数。 | doi = 10.1109/SFCS.1995.492583 | location = Los Alamitos, CA | mr = 1619103 | pages = 528–537 | publisher = IEEE Comput. Soc. Press In 1982, Richard Feynman suggested an initial approach to quantizing a model of cellular automata. In 1985, David Deutsch presented a formal development of the subject. Later, Gerhard Grössing and Anton Zeilinger introduced the term "quantum cellular automata" to refer to a model they defined in 1988, although their model had very little in common with the concepts developed by Deutsch and so has not been developed significantly as a model of computation. 1982年，理查德·费曼（Richard Feynman）提出了一个初步的方法来量化一个细胞自动机模型。1985年，大卫·多伊奇（David Deutsch）提出了一个正式的发展主题。后来，格哈德·格罗辛(Gerhard Grössing)和安东·泽林格(Anton Zeilinger)引入了“量子细胞自动机”(quantum cellular automata)一词，指的是他们在1988年定义的一个模型，因为他们的模型与多伊奇(Deutsch)提出的概念几乎没有共同之处，因此没有被明显地发展成为一个计算模型。 | title = Proc. 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995) | year = 1995| title-link = Symposium on Foundations of Computer Science }}.
  2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 C. Pérez-Delgado and D. Cheung, "Local Unitary Quantum Cellular Automata", Phys. Rev. A 76, 032320, 2007. See also arXiv:0709.0006 (quant-ph)
  3. ↑ 3.0 3.1 The first formal model of quantum cellular automata to be researched in depth was that introduced by John Watrous. as well as Christoph Dürr, Huong LêThanh, and Miklos Santha, Jozef Gruska. and Pablo Arrighi. However it was later realised that this definition was too loose, in the sense that some instances of it allow superluminal signalling. of Benjamin Schumacher and Reinhard Werner, Bruce Boghosian and Washington Taylor, and Peter Love and Bruce Boghosian as a means of simulating quantum lattice gases, motivated by the use of "classical" cellular automata to model classical physical phenomena such as gas dispersion. Criteria determining when a quantum cellular automaton (QCA) can be described as quantum lattice gas automaton (QLGA) were given by Asif Shakeel and Peter Love. 第一个深入研究的量子细胞自动机的正式模型是由约翰·瓦特罗斯（John Watrous），以及克里斯托弗·杜尔（Christoph Dürr），Huong lêthanh，和米克洛斯·桑塔 Miklos Santha，约瑟夫·格鲁斯卡（Jozef Gruska），还有巴勃罗·阿瑞基（Pablo Arrighi）提出的。然而后来本杰明·舒马赫（Benjamin Schumacher）和莱因哈德·维尔纳（Reinhard Werner），布鲁斯·博格斯（Bruce Boghosian）和华盛顿·泰勒（Washington Taylor），以及彼得·洛夫（Peter Love）和布鲁斯·博格斯（Bruce Boghosian）意识到这个定义过于宽松，在某种意义上，它的一些实例允许超光速信号。作为模拟量子晶格气体的一种手段，其动机是使用“经典”细胞自动机对诸如气体扩散等经典物理现象进行建模。阿西夫·沙克（Asif shakel）和彼得·洛夫（Peter Love）给出了确定量子细胞自动机(QCA)何时可以被描述为量子晶格气体自动机(QLGA)的标准。 D.J. Shepherd, T. Franz, R.F. Werner: Universally programmable Quantum Cellular Automaton. Phys. Rev. Lett. 97, 020502 (2006) D.J.谢泼德, T.弗朗茨, R.F.维尔纳：通用可编程的量子细胞自动机。理论物理。Rev. Lett. 97,020502 (2006)
  4. ↑ 4.0 4.1 P. Arrighi, R. Fargetton, Z. Wang, Intrinsically universal one-dimensional quantum cellular automata in two flavours, Fundamenta Informaticae Vol.91, No.2, pp.197-230, (2009). See also (quant-ph)
  5. ↑ 5.0 5.1 P. Arrighi, J. Grattage, A quantum Game of Life, Proceedings of JAC 2010, Turku, December 2010. TUCS Lecture Notes 13, 31-42, (2010). See also (quant-ph) and (Companion Website)
  6. ↑ 6.0 6.1 6.2 6.3 6.4 6.5 B. Schumacher and R. Werner, "Reversible quantum cellular automata", quant-ph/0405174
  7. ↑ 7.0 7.1 7.2 7.3 7.4 7.5 Pablo Arrighi, Vincent Nesme, Reinhard Werner, One-dimensional quantum cellular automata over finite, unbounded configurations. See also (quant-ph)
  8. ↑ 8.0 8.1 8.2 8.3 Pablo Arrighi, Vincent Nesme, Reinhard Werner, N-dimensional quantum cellular automata. See also (quant-ph)
  9. ↑ 9.0 9.1 R. Feynman, "Simulating physics with computers", Int. J. Theor. Phys. 21, 1982: pp. 467–488.
  10. ↑ 10.0 10.1 D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer" Proceedings of the Royal Society of London A 400 (1985), pp. 97–117.
  11. ↑ 11.0 11.1 G. Grossing and A. Zeilinger, "Quantum cellular automata", Complex Systems 2 (2), 1988: pp. 197–208 and 611–623.
  12. ↑ 12.0 12.1 W. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996.
  13. ↑ 13.0 13.1 13.2 C. Dürr and M. Santha, "A decision procedure for unitary linear quantum cellular automata", quant-ph/9604007 .
  14. ↑ 14.0 14.1 14.2 C. Dürr, H. LêTanh, M. Santha, "A decision procedure for well-formed linear quantum cellular automata", Rand. Struct. Algorithms 11, 1997: pp. 381–394. See also cs.DS/9906024.
  15. ↑ 15.0 15.1 15.2 J. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999: Section 4.3.
  16. ↑ 16.0 16.1 Pablo Arrighi, An algebraic study of unitary one dimensional quantum cellular automata, Proceedings of MFCS 2006, LNCS 4162, (2006), pp122-133. See also quant-ph/0512040
  17. ↑ 17.0 17.1 S. Richter and R.F. Werner, "Ergodicity of quantum cellular automata", J. Stat. Phys. 82, 1996: pp. 963–998. See also cond-mat/9504001
  18. ↑ 18.0 18.1 D. Meyer, "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, 1996: pp. 551–574. See also quant-ph/9604003.
  19. ↑ 19.0 19.1 D. Meyer, "On the absence of homogeneous scalar unitary cellular automata'", Physics Letters A 223, 1996: pp. 337–340. See also quant-ph/9604011.
  20. ↑ 20.0 20.1 B. Boghosian and W. Taylor, "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions", Physical Review E 57, 1998: pp. 54–66.
  21. ↑ 21.0 21.1 P. Love and B. Boghosian, "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, 2005, pp. 335–354.
  22. ↑ 22.0 22.1 B. Chophard and M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998.
  23. ↑ 23.0 23.1 Shakeel, Asif; Love, Peter J. (2013-09-01). "When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?". Journal of Mathematical Physics. 54 (9): 092203. arXiv:1209.5367. Bibcode:2013JMP....54i2203S. doi:10.1063/1.4821640. ISSN 0022-2488.
取自“https://wiki.swarma.org/index.php?title=量子元胞自动机&oldid=32593”