English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

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