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.
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.
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS's for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca's). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be space efficient. As a further result, if the 2qcca can use a quantum counter instead of a classical one, then the protocol can even be public, also known as Arthur-Merlin games. We also investigate the computational power of 2pca's and 2qcca's as language recognizers. We show that bounded-error 2pca's can be more powerful than their deterministic counterparts by giving a bounded-error simulation of their nondeterministic counterparts. Then, we present a new programming technique for bounded-error 2qcca's and show that they can recognize a language which seems not to be recognized by any bounded-error 2pca. We also obtain some interesting results for bounded-error 1-pebble quantum finite automata based on this new technique. Lastly, we prove a conjecture posed by Ravikumar (FSTTCS 1992) regarding 1-pebble probabilistic finite automata, i.e. they can recognize some nonstochastic languages with bounded error.
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.
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.