Quantum branching programs and space-bounded nonuniform quantum complexity

DOI10.1016/j.tcs.2004.12.031zbMath1080.68029arXivquant-ph/0403164OpenAlexW2015812914MaRDI QIDQ1779302

Martin Sauerhoff, Detlef Sieling

Publication date: 1 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0403164

zbMATH Keywords

SimulationOBDDQuantum computationLower boundSpace complexityBranching programQuantum Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items

Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Nondeterministic unitary OBDDs ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Computing Boolean Functions via Quantum Hashing ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ On quantum realisation of Boolean functions by the fingerprinting technique ⋮ On the average sensitivity of the weighted sum function ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Comparative complexity of quantum and classical OBDDs for total and partial functions ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ The simplified weighted sum function and its average sensitivity ⋮ On the computational power of probabilistic and quantum branching program

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Reversible space equals deterministic space
• Time-space tradeoffs for branching programs
• Computational complexity of uniform quantum circuit families and quantum Turing machines
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• On the complexity of simulating space-bounded quantum computations
• Space-bounded quantum complexity
• Local Transition Functions of Quantum Turing Machines
• Exponential separation of quantum and classical communication complexity
• On quantum and probabilistic communication
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computability
• Quantum Complexity Theory
• Branching Programs and Binary Decision Diagrams
• Efficient discrete approximations of quantum gates
• Communication Complexity
• The Kantorovich and Some Related Inequalities
• Quantum theory: concepts and methods
• On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions