0000000000610388

AUTHOR

Jibran Rashid

showing 2 related works from this author

Implications of quantum automata for contextuality

2014

We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …

Discrete mathematicsProbabilistic finite automataTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESQuantum automata0102 computer and information sciencesConstruct (python library)Nonlinear Sciences::Cellular Automata and Lattice Gases01 natural sciencesKochen–Specker theoremTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematics0103 physical sciencesQuantum finite automataPromise problem010306 general physicsComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Implications of quantum automata for contextuality

2014

We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results: - There is a promise problem solvable by an exact two-way QFA in exponential expected time, but not by any bounded-error sublogarithmic space probabilistic Turing machine (PTM). - There is a promise problem solvable by an exact two-way QFA in quadratic expected time, but not by any bounded-error $ o(\log \log n) $-space PTMs in polynomial expected time. The same problem can be solvable by a one-way Las Vegas (or exact two-way) QFA with quantum head in linear (expected) time. - There is a promise problem so…

FOS: Computer and information sciencesQuantum PhysicsComputer Science - Computational ComplexityFormal Languages and Automata Theory (cs.FL)FOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Quantum Physics (quant-ph)Computer Science::Formal Languages and Automata Theory
researchProduct