Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1205.5395

Turing-equivalent automata using a fixed-size quantum memory

Abuzer Yakaryılmaz

Published May 24, 2012• 5 citations
arXivHTMLPDF

Abstract

In this paper, we introduce a new public quantum interactive proof system and the first quantum alternating Turing machine: qAM proof system and qATM, respectively. Both are obtained from their classical counterparts (Arthur-Merlin proof system and alternating Turing machine, respectively,) by augmenting them with a fixed-size quantum register. We focus on space-bounded computation, and obtain the following surprising results: Both of them with constant-space are Turing-equivalent. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system, (the nonmembers do not need to be rejected with high probability), and we show that any Turing-recognizable language can be recognized by a constant-space qATM even with one-way input head. For strong proof systems, where the nonmembers must be rejected with high probability, we show that the known space-bounded classical private protocols can also be simulated by our public qAM system with the same space bound. Besides, we introduce a strong version of qATM: The qATM that must halt in every computation path. Then, we show that strong qATMs (similar to private ATMs) can simulate deterministic space with exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one-level. The method behind the main results is a new public protocol cleverly using its fixed-size quantum register. Interestingly, the quantum part of this public protocol cannot be simulated by any space-bounded classical protocol in some cases.

DOI
10.48550/arxiv.1205.5395

Related papers

Public-qubits versus private-coins.

Abuzer Yakaryılmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on spacebounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems not only can simulate all known space-bounded private-coin protocols, but also implements some protocols that are either not implementable by IP systems or currently not known to be simulated by IP systems. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system (the nonmembers do not need to be rejected with high probability), and, different from the classical case, our protocol has perfect-completeness (the members are accepted exactly). For strong proof system, where the nonmembers must be rejected with high probability, we show that the known space-bounded private-coin protocols can also be simulated by qAM systems with the same space bound. In case of constant-space and log-space IP systems, the best known lower bounds are ASPACE(n) and EXP, respectively. We obtain better lower bounds for the corresponding qAM systems: Each language in NP has a constant-space (exp-time) qAM system, there is an NEXP-complete language having a constant-space qAM system, and each language in NEXP has a log-space qAM system.

Electronic colloquium on computational complexity•Jan 1, 2012•16 citations

Quantum alternation

Abuzer Yakaryılmaz

We introduce quantum alternation as a generalization of quantum nondeterminism. We define q-alternating Turing machine (qATM) by augmenting alternating Turing machine with constant-size quantum memory. We show that one-way constant-space qATMs (1AQFAs) are Turing equivalent. Then, we introduce strong version of qATM by requiring to halt in every computation path and we show that strong qATMs can simulate deterministic spacewith exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one level. We also focus on realtime versions of 1AQFAs (rtAQFAs) and obtain many results: rtAQFAs can recognize a PSPACE-complete problem; they cannot be simulated by sublinear deterministic Turing machines; for any level of polynomial hierarchy, say k , there exists a complete language that can be recognized by rtAFAs with only ( k +1) alternations; and polynomial hierarchy lies in its log-space q-alternation counterpart.

Lobachevskii Journal of Mathematics•Nov 1, 2016•4 citations

Classical and quantum computation with small space bounds (PhD thesis)

Abuzer Yakaryılmaz

In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.

arXiv:1102.0378•Feb 2, 2011•8 citations

Magic coins are useful for small-space quantum machines

A. C. Cem Say, Abuzer Yakaryılmaz

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double logarithmic space, it is known that such “magic coins” give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton (2qcfa) that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.

arXiv:1411.7647•Quantum Information and Computation•Sep 1, 2017•13 citations

Space-bounded quantum computation

John Watrous, Eric Bach

In this dissertation, we investigate the computational power of quantum Turing machines operating in bounded space. First, we consider space-bounds that are space-constructible and at least logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.

•Jan 1, 1998•19 citations

Relationships between quantum and classical space-bounded complexity classes

John Watrous

This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.

IEEE Conference on Computational Complexity (CCC)•Nov 27, 2002•13 citations
In this paper, we introduce a new public quantum interactive proof system and the first quantum alternating Turing machine: qAM proof system and qATM, respectively. Both are obtained from their classical counterparts (Arthur-Merlin proof system and alternating Turing machine, respectively,) by augmenting them with a fixed-size quantum register. We focus on space-bounded computation, and obtain the following surprising results: Both of them with constant-space are Turing-equivalent. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system, (the nonmembers do not need to be rejected with high probability), and we show that any Turing-recognizable language can be recognized by a constant-space qATM even with one-way input head. For strong proof systems, where the nonmembers must be rejected with high probability, we show that the known space-bounded classical private protocols can also be simulated by our public qAM system with the same space bound. Besides, we introduce a strong version of qATM: The qATM that must halt in every computation path. Then, we show that strong qATMs (similar to private ATMs) can simulate deterministic space with exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one-level. The method behind the main results is a new public protocol cleverly using its fixed-size quantum register. Interestingly, the quantum part of this public protocol cannot be simulated by any space-bounded classical protocol in some cases.
We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on spacebounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems not only can simulate all known space-bounded private-coin protocols, but also implements some protocols that are either not implementable by IP systems or currently not known to be simulated by IP systems. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system (the nonmembers do not need to be rejected with high probability), and, different from the classical case, our protocol has perfect-completeness (the members are accepted exactly). For strong proof system, where the nonmembers must be rejected with high probability, we show that the known space-bounded private-coin protocols can also be simulated by qAM systems with the same space bound. In case of constant-space and log-space IP systems, the best known lower bounds are ASPACE(n) and EXP, respectively. We obtain better lower bounds for the corresponding qAM systems: Each language in NP has a constant-space (exp-time) qAM system, there is an NEXP-complete language having a constant-space qAM system, and each language in NEXP has a log-space qAM system.
We introduce quantum alternation as a generalization of quantum nondeterminism. We define q-alternating Turing machine (qATM) by augmenting alternating Turing machine with constant-size quantum memory. We show that one-way constant-space qATMs (1AQFAs) are Turing equivalent. Then, we introduce strong version of qATM by requiring to halt in every computation path and we show that strong qATMs can simulate deterministic spacewith exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one level. We also focus on realtime versions of 1AQFAs (rtAQFAs) and obtain many results: rtAQFAs can recognize a PSPACE-complete problem; they cannot be simulated by sublinear deterministic Turing machines; for any level of polynomial hierarchy, say k , there exists a complete language that can be recognized by rtAFAs with only ( k +1) alternations; and polynomial hierarchy lies in its log-space q-alternation counterpart.
In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double logarithmic space, it is known that such “magic coins” give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton (2qcfa) that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.
In this dissertation, we investigate the computational power of quantum Turing machines operating in bounded space. First, we consider space-bounds that are space-constructible and at least logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.
This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.