Abstract:
In this paper we introduce classically time-controlled quantum automata or CTQA, which is a slight but reasonable modification of Moore-Crutchfield quantum finite automata that uses time-dependent evolution operators and a scheduler defining how long each operator will run. Surprisingly enough, time-dependent evolutions provide a significant change in the computational power of quantum automata with respect to a discrete quantum model. Furthermore, 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. © 2018, Springer Nature Switzerland AG.
Registro:
Documento: |
Artículo
|
Título: | Classically time-controlled quantum automata |
Autor: | Díaz-Caro, A.; Villagra, M.; Martin-Vide C.; Vega-Rodriguez M.A.; Fagan D.; O'Neill M. |
Filiación: | Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes, Roque Sáenz Peña 352, Bernal, Buenos Aires, B1876BXD, Argentina Instituto de Ciencias de la Computación, CONICET-Universidad de Buenos Aires, Pabellón 1, Ciudad Universitaria, Buenos Aires, C1428EGA, Argentina Núcleo de Investigación y Desarrollo Tecnológico, Universidad Nacional de Asunción, San Lorenzo, Asunción, 2169, Paraguay
|
Palabras clave: | Bounded error; Cutpoint language; Quantum computing; Quantum finite automata; Time-dependent unitary evolution; Finite automata; Bounded errors; Cut-point; Quantum Computing; Quantum finite automata; Time dependent; Quantum computers |
Año: | 2018
|
Volumen: | 11324 LNCS
|
Página de inicio: | 266
|
Página de fin: | 278
|
DOI: |
http://dx.doi.org/10.1007/978-3-030-04070-3_21 |
Título revista: | 7th International Conference on the Theory and Practice of Natural Computing, TPNC 2018
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v11324LNCS_n_p266_DiazCaro |
Referencias:
- Ambainis, A., Freivalds, R., 1-way quantum finite automata: Strengths, weaknesses and generalizations (1998) Proceedings of the 39Th Annual Symposium on Foundations of Computer Science (FOCS), pp. 332-341
- Ambainis, A., Watrous, J., Two-way finite automata with quantum and classical states (2002) Theor. Comput. Sci., 287 (1), pp. 299-311
- Brodsky, A., Pippenger, N., Characterizations of 1-way quantum finite automata (2002) SIAM J. Comput., 31 (5), pp. 1456-1478
- Díaz-Caro, A., A lambda calculus for density matrices with classical and probabilistic controls (2017) Programming Languages and Systems (APLAS 2017). Lecture Notes in Computer Science, 10695, pp. 448-467. , Chang, B.Y.E. (ed.), Springer, Cham
- Green, A.S., Lumsdaine, P.L., Ross, N.J., Selinger, P., Valiron, B., Quipper: A scalable quantum programming language (2013) ACM SIGPLAN Notices (PLDI 2013, 48 (6), pp. 333-342
- Knill, E.H., (1996) Conventions for Quantum Pseudocode, , Technical report LA-UR-96-2724, Los Alamos National Laboratory
- Moore, C., Crutchfield, J.P., Quantum automata and quantum grammars (2000) Theor. Comput. Sci., 237 (1-2), pp. 275-306
- Nishimura, H., Yamakami, T., An application of quantum finite automata to interactive proof systems (2009) J. Comput. Syst. Sci., 75 (4), pp. 255-269
- Paykin, J., Rand, R., Zdancewic, S., Qwire: A core language for quantum circuits (2017) Proceedings of the 44Th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, pp. 846-858. , ACM, New York
- Say, A.C.C., Yakaryılmaz, A., Quantum finite automata: A modern introduction (2014) Computing with New Resources. LNCS, 8808, pp. 208-222. , https://doi.org/10.1007/978-3-319-13350-816, Calude, C.S., Freivalds, R., Kazuo, I. (eds.), Springer, Cham
- Say, A., Yakaryilmaz, A., Magic coins are useful for small-space quantum machines (2017) Quantum Inf. Comput, 17 (11-12), pp. 1027-1043
- Selinger, P., Towards a quantum programming language (2004) Math. Struct. Comput. Sci., 14 (4), pp. 527-586
- Selinger, P., Valiron, B., A lambda calculus for quantum computation with classical control (2006) Math. Struct. Comput. Sci., 16 (3), pp. 527-552
- Villagra, M., Yamakami, T., Quantum and reversible verification of proofs using constant memory space (2014) TPNC 2014. LNCS, 8890, pp. 144-156. , https://doi.org/10.1007/978-3-319-13749-013, Dediu, A.-H., Lozano, M., Martín-Vide, C. (eds.), Springer, Cham
- Villagra, M., Yamakami, T., Quantum state complexity of formal languages (2015) DCFS 2015. LNCS, 9118, pp. 280-291. , https://doi.org/10.1007/978-3-319-19225-324, Shallit, J., Okhotin, A. (eds.), Springer, Cham
- Yamakami, T., One-way reversible and quantum finite automata with advice (2014) Inf. Comput., 239, pp. 122-148
- Zheng, S., Qiu, D., Gruska, J., Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata (2015) Inf. Comput., 241, pp. 197-214
Citas:
---------- APA ----------
Díaz-Caro, A., Villagra, M., Martin-Vide C., Vega-Rodriguez M.A., Fagan D. & O'Neill M.
(2018)
. Classically time-controlled quantum automata. 7th International Conference on the Theory and Practice of Natural Computing, TPNC 2018, 11324 LNCS, 266-278.
http://dx.doi.org/10.1007/978-3-030-04070-3_21---------- CHICAGO ----------
Díaz-Caro, A., Villagra, M., Martin-Vide C., Vega-Rodriguez M.A., Fagan D., O'Neill M.
"Classically time-controlled quantum automata"
. 7th International Conference on the Theory and Practice of Natural Computing, TPNC 2018 11324 LNCS
(2018) : 266-278.
http://dx.doi.org/10.1007/978-3-030-04070-3_21---------- MLA ----------
Díaz-Caro, A., Villagra, M., Martin-Vide C., Vega-Rodriguez M.A., Fagan D., O'Neill M.
"Classically time-controlled quantum automata"
. 7th International Conference on the Theory and Practice of Natural Computing, TPNC 2018, vol. 11324 LNCS, 2018, pp. 266-278.
http://dx.doi.org/10.1007/978-3-030-04070-3_21---------- VANCOUVER ----------
Díaz-Caro, A., Villagra, M., Martin-Vide C., Vega-Rodriguez M.A., Fagan D., O'Neill M. Classically time-controlled quantum automata. Lect. Notes Comput. Sci. 2018;11324 LNCS:266-278.
http://dx.doi.org/10.1007/978-3-030-04070-3_21