A Decision Procedure for Well-Formed Linear Quantum Cellular Automata
作者： Christoph Dürr , Huong Lê Thanh , Miklos Santha
关键词:
摘要: In this paper we introduce a new quantum computation model, the linear cellular automaton. Well-formedness is an essential property for any computing device since it enables us to define probability of configuration in observation as squared magnitude its amplitude. We give efficient algorithm which decides if automaton well-formed. The complexity O(n2) input has continuous neighborhood.
springer.com
core.ac.uk
arxiv-vanity.com参考文章(19)
Lester Randolph Ford, Flows in networks ,(1962)
S. Lloyd, A Potentially Realizable Quantum Computer Science. ,vol. 261, pp. 1569- 1571 ,(1993) , 10.1126/SCIENCE.261.5128.1569
Ethan Bernstein, Umesh Vazirani, Quantum complexity theory Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 11- 20 ,(1993) , 10.1145/167088.167097
S. Lloyd, Envisioning a Quantum Supercomputer Science. ,vol. 263, pp. 695- 695 ,(1994) , 10.1126/SCIENCE.263.5147.695
S. Amoroso, Y.N. Patt, Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures Journal of Computer and System Sciences. ,vol. 6, pp. 448- 464 ,(1972) , 10.1016/S0022-0000(72)80013-8
Richard P. Feynman, Quantum Mechanical Computers Foundations of Physics. ,vol. 16, pp. 507- 531 ,(1986) , 10.1007/BF01886518
Rapid Solution of Problems by Quantum Computation Proceedings of The Royal Society A: Mathematical, Physical and Engineering Sciences. ,vol. 439, pp. 553- 558 ,(1992) , 10.1098/RSPA.1992.0167
Robert Tarjan, Depth-First Search and Linear Graph Algorithms SIAM Journal on Computing. ,vol. 1, pp. 146- 160 ,(1972) , 10.1137/0201010
D.R. Simon, On the power of quantum computation foundations of computer science. pp. 116- 123 ,(1994) , 10.1109/SFCS.1994.365701
J. Watrous, On one-dimensional quantum cellular automata foundations of computer science. pp. 528- 537 ,(1995) , 10.1109/SFCS.1995.492583