Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
ECCC BOOKS, LECTURES AND SURVEYS > CLASSICAL AND QUANTUM COMPUTATION WITH SMALL SPACE BOUNDS:
Abuzer Yakaryilmaz

Classical and quantum computation with small space bounds

Download

Bogazici University, Istanbul, January 2011

Abstract

In this thesis, we introduce a new quantum Turing machine 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 quantum Turing machines in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by quantum Turing machines 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 quantum Turing machines; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic quantum Turing machines is given.

Secondly, we consider constant space-bounded quantum Turing machines in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata 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 probabilistic and two-way classical-head quantum finite automata are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce probabilistic and quantum finite automata with postselection with their bounded error language classes, and give many characterizations of them.

Thirdly, the computational power of realtime quantum finite automata augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Parallelly, some results on counter and pushdown automata are obtained.

Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight. Moreover, the same question is investigated for some other kinds of realtime machines and several nonregular languages recognized by them in small space bounds are presented.

Table of Contents (short)
  1. INTRODUCTION
  2. SPACE-BOUNDED COMPUTATION
  3. A NEW KIND OF QUANTUM MACHINE
    1. The General Framework for Quantum Machines
    2. Quantum Turing Machines
    3. Quantum Pushdown Automata
    4. Quantum Counter Automata
    5. Nondeterministic Quantum Machines
  4. SUBLOGARITHMIC-SPACE UNBOUNDED-ERROR COMPUTATION
    1. Unbounded Error Results
      1. Probabilistic versus Quantum Computation with Sublogarithmic Space
      2. Languages Recognized by Kondacs-Watrous Quantum Finite Automata
    2. Nondeterministic Quantum Computation
  5. CONSTANT-SPACE BOUNDED-ERROR COMPUTATION
    1. Probabilistic and Quantum Automata with Resetting
    2. Succinctness of Two-Way Models
    3. Probabilistic and Quantum Automata with Postselection
  6. WRITE-ONLY MEMORY
    1. Realtime Quantum Finite Automata with Incremental-Only Counters
    2. Realtime Quantum Finite Automata with Push-Only Stacks
    3. Realtime Quantum Finite Automata with Write-Only Memories
  7. SUBLINEAR-SPACE REALTIME TURING MACHINES
  8. RELATED WORK
  9. CONCLUSION
  1. LOCAL CONDITIONS FOR QUANTUM MACHINES
  2. QUANTUM COMPUTATION
  • REFERENCES
 Table of Contents (long)
  1. INTRODUCTION
  2. SPACE-BOUNDED COMPUTATION
    1. Preliminaries
      1. Basic Notation
      2. Basic Terminology
      3. Language Recognition
    2. Turing Machines
    3. Pushdown Automata
    4. Counter Automata
    5. Formal Definition of Classical Machines
    6. Computation of Machines
      1. Deterministic Computation
      2. Nondeterministic Computation
      3. Alternating Computation
      4. Probabilistic Computation
      5. Quantum Computation
    7. Space Classes
  3. A NEW KIND OF QUANTUM MACHINE
    1. The General Framework for Quantum Machines
    2. Quantum Turing Machines
      1. Two-Way Quantum Finite Automata
      2. Unidirectional Quantum Turing Machines
      3. Quantum Turing Machines with Classical Heads
      4. Realtime Quantum Finite Automata
      5. Quantum Turing Machines with Restricted Measurements
    3. Quantum Pushdown Automata
    4. Quantum Counter Automata
    5. Nondeterministic Quantum Machines
  4. SUBLOGARITHMIC-SPACE UNBOUNDED-ERROR COMPUTATION
    1. Unbounded Error Results
      1. Probabilistic versus Quantum Computation with Sublogarithmic Space
      2. Languages Recognized by Kondacs-Watrous Quantum Finite Automata
    2. Nondeterministic Quantum Computation
      1. Basic Facts
      2. Languages Recognized with One-Sided Error
      3. Space Efficiency of Nondeterministic Quantum Finite Automata
      4. Languages Recognized with Two-Sided Error
      5. Closure Properties
  5. CONSTANT-SPACE BOUNDED-ERROR COMPUTATION
    1. Probabilistic and Quantum Automata with Resetting
      1. Definitions
      2. Basic Facts
      3. Computational Powers of Realtime Probabilistic Finite Automata with Restart
      4. Computational Powers of Realtime Quantum Finite Automata with Restart
    2. Succinctness of Two-Way Models
    3. Probability Amplification
      1. Improved Algorithms for UPAL Language
      2. A Realtime Quantum Finite Automata with Restart Algorithm for UPAL Language
      3. An Improved Algorithm for PAL Language
    4. Probabilistic and Quantum Automata with Postselection
      1. Definitions
      2. Characterization of Realtime Postselection Automata
      3. Latvian Postselection Automata
  6. WRITE-ONLY MEMORY
    1. Definitions
    2. Basic Facts
    3. Realtime Quantum Finite Automata with Incremental-Only Counters
      1. Bounded Error
      2. Unbounded Error
    4. Realtime Quantum Finite Automata with Push-Only Stacks
    5. Realtime Quantum Finite Automata with Write-Only Memories
  7. SUBLINEAR-SPACE REALTIME TURING MACHINES
  8. RELATED WORK
    1. Counter and Pushdown Automata
    2. Promise Problems
    3. Multihead Finite Automata
  9. CONCLUSION
  1. LOCAL CONDITIONS FOR QUANTUM MACHINES
    1. Quantum Turing Machines
    2. Quantum Pushdown Automata
  2. QUANTUM COMPUTATION
  • REFERENCES
 Number of pages: 184

ISSN 1433-8092 | Imprint