Universality of quantum Turing machines with deterministic control

被引：5
|
作者：
Mateus, P. [1 ]
Sernadas, A.
Souto, A.
机构：
[1] Univ Lisbon, Inst Super Tecn, Dept Matemat, P-1699 Lisbon, Portugal
来源：
JOURNAL OF LOGIC AND COMPUTATION | 2017年 / 27卷 / 01期
关键词：
Quantum computation; computational complexity; quantum Kolmogorov complexity; COMPLEXITY;
D O I：
10.1093/logcom/exv008
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Asimple notion of quantum Turing machine with deterministic, classical control is proposed and shown to be powerful enough to compute any unitary transformation that is computable by a finitely generated quantum circuit. Anefficient universal machine with the s-m-n property is presented. The BQPclass is recovered. Arobust notion of plain Kolmogorov complexity of quantum states is proposed and compared with those previously reported in the literature.
引用
收藏
页码：1 / 19
页数：19
相关论文
共 50 条
  • [1] Turing machines based on quantum logic and their universality
    Li, Yong-Ming
    Li, Ping
    Jisuanji Xuebao/Chinese Journal of Computers, 2012, 35 (07): : 1407 - 1420
  • [2] Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
    Lemus, Mariano
    Faleiro, Ricardo
    Mateus, Paulo
    Paunkovic, Nikola
    Souto, Andre
    QUANTUM, 2024, 8
  • [3] Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms
    Burgin, Mark
    Eberbach, Eugene
    FUNDAMENTA INFORMATICAE, 2009, 91 (01) : 53 - 77
  • [4] Small deterministic Turing machines
    Universitaet Hamburg, Hamburg, Germany
    Theor Comput Sci, 2 (241-255):
  • [5] Small deterministic Turing machines
    Kudlek, M
    THEORETICAL COMPUTER SCIENCE, 1996, 168 (02) : 241 - 255
  • [6] Towards Observable Quantum Turing Machines: Fundamentals, Computational Power, and Universality
    Perdrix, Simon
    INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING, 2011, 7 (04) : 291 - 311
  • [7] On reversible Turing machines and their function universality
    Axelsen, Holger Bock
    Gluck, Robert
    ACTA INFORMATICA, 2016, 53 (05) : 509 - 543
  • [8] Approximation and universality of fuzzy Turing machines
    Li YongMing
    SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES, 2008, 51 (10): : 1445 - 1465
  • [9] Approximation and universality of fuzzy Turing machines
    LI YongMing College of Computer Science
    Science in China(Series F:Information Sciences), 2008, (10) : 1445 - 1465
  • [10] Fuzzy Turing Machines: Variants and Universality
    Li, Yongming
    IEEE TRANSACTIONS ON FUZZY SYSTEMS, 2008, 16 (06) : 1491 - 1502
12345