0000000000222277

AUTHOR

Andrej Dubrovsky

showing 2 related works from this author

Quantum Query Complexity for Some Graph Problems

2004

The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.

CombinatoricsQuantum queryGraph (abstract data type)Computer Science::Computational ComplexityUpper and lower boundsMathematics
researchProduct

Space-Efficient 1.5-Way Quantum Turing Machine

2001

1.5QTM is a sort of QTM (Quantum Turing Machine) where the head cannot move left (it can stay where it is and move right). For computations is used other - work tape. In this paper will be studied possibilities to economize work tape space more than the same deterministic Turing Machine can do (for some of the languages). As an example language (0i1i|i ≥ 0) is chosen, and is proved that this language could be recognized by deterministic Turing machine using log(i) cells on work tape , and 1.5QTM can recognize it using constant cells quantity.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineSuper-recursive algorithmComputer scienceProbabilistic Turing machineComputationDescription numberMultitape Turing machineDSPACElaw.inventionTuring machinesymbols.namesakeNon-deterministic Turing machinelawAlgorithm characterizationsPSPACEWolfram's 2-state 3-symbol Turing machineTuring machine examplesNSPACETuring reductionsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineRegister machine
researchProduct