Classically Time-Controlled Quantum Automata: Definition and Properties
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909802910711808 |
|---|---|
| author | Díaz-Caro, Alejandro Villagra, Marcos |
| author_facet | Díaz-Caro, Alejandro Villagra, Marcos |
| contents | In this paper, we introduce classically time-controlled quantum automata or CTQA, which is a reasonable modification of Moore-Crutchfield quantum finite automata that uses time-dependent evolution and a "scheduler" defining how long each Hamiltonian will run. Surprisingly enough, time-dependent evolution provides a significant change in the computational power of quantum automata with respect to a discrete quantum model. Indeed, we show that if a scheduler is not computationally restricted, then a CTQA could even decide the Halting problem. In order to unearth the computational capabilities of CTQAs we study the case of a computationally restricted scheduler. In particular, we showed that depending on the type of restriction imposed on the scheduler, a CTQA can (i) recognize non-regular languages with cut-point, even in the presence of Karp-Lipton advice, and (ii) recognize non-regular promise languages with bounded-error. Furthermore, we study the cutpoint-union of cutpoint languages by introducing a new model of Moore-Crutchfield quantum finite automata with a rotating tape head. CTQA presents itself as a new model of computation that provides a different approach to a formal study of "classical control, quantum data" schemes in quantum computing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1807_05385 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Classically Time-Controlled Quantum Automata: Definition and Properties Díaz-Caro, Alejandro Villagra, Marcos Formal Languages and Automata Theory Computational Complexity Quantum Physics 68Q05, 68Q45, 81P68 F.1.1 In this paper, we introduce classically time-controlled quantum automata or CTQA, which is a reasonable modification of Moore-Crutchfield quantum finite automata that uses time-dependent evolution and a "scheduler" defining how long each Hamiltonian will run. Surprisingly enough, time-dependent evolution provides a significant change in the computational power of quantum automata with respect to a discrete quantum model. Indeed, we show that if a scheduler is not computationally restricted, then a CTQA could even decide the Halting problem. In order to unearth the computational capabilities of CTQAs we study the case of a computationally restricted scheduler. In particular, we showed that depending on the type of restriction imposed on the scheduler, a CTQA can (i) recognize non-regular languages with cut-point, even in the presence of Karp-Lipton advice, and (ii) recognize non-regular promise languages with bounded-error. Furthermore, we study the cutpoint-union of cutpoint languages by introducing a new model of Moore-Crutchfield quantum finite automata with a rotating tape head. CTQA presents itself as a new model of computation that provides a different approach to a formal study of "classical control, quantum data" schemes in quantum computing. |
| title | Classically Time-Controlled Quantum Automata: Definition and Properties |
| topic | Formal Languages and Automata Theory Computational Complexity Quantum Physics 68Q05, 68Q45, 81P68 F.1.1 |
| url | https://arxiv.org/abs/1807.05385 |