Quantum branching programs and space-bounded nonuniform quantum complexity
From MaRDI portal
Abstract: In this paper, the space complexity of nonuniform quantum computations is investigated. The model chosen for this are quantum branching programs, which provide a graphic description of sequential quantum algorithms. In the first part of the paper, simulations between quantum branching programs and nonuniform quantum Turing machines are presented which allow to transfer lower and upper bound results between the two models. In the second part of the paper, different variants of quantum OBDDs are compared with their deterministic and randomized counterparts. In the third part, quantum branching programs are considered where the performed unitary operation may depend on the result of a previous measurement. For this model a simulation of randomized OBDDs and exponential lower bounds are presented.
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1696662 (Why is no real title available?)
- scientific article; zbMATH DE number 1335895 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- scientific article; zbMATH DE number 2086634 (Why is no real title available?)
- scientific article; zbMATH DE number 1839432 (Why is no real title available?)
- Branching Programs and Binary Decision Diagrams
- Communication Complexity
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Determinism versus nondeterminism for linear time RAMs with memory restrictions
- Efficient discrete approximations of quantum gates
- Exponential separation of quantum and classical communication complexity
- Local transition functions of quantum Turing machines
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- On the complexity of simulating space-bounded quantum computations
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Complexity Theory
- Quantum Computability
- Quantum theory: concepts and methods
- Reversible space equals deterministic space
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Space-bounded quantum complexity
- The Kantorovich and Some Related Inequalities
- Time-space trade-off lower bounds for randomized computation of decision problems
- Time-space tradeoffs for branching programs
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
Cited in
(22)- The simplified weighted sum function and its average sensitivity
- Quantum online streaming algorithms with logarithmic memory
- Classical and Quantum Computations with Restricted Memory
- Space complexity of streaming algorithms on universal quantum computers
- On complexity of classical simulation of quantum branching programs
- scientific article; zbMATH DE number 2086634 (Why is no real title available?)
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On the computational power of probabilistic and quantum branching program
- Error-Free Affine, Unitary, and Probabilistic OBDDs
- Nondeterministic unitary OBDDs
- On quantum realisation of Boolean functions by the fingerprinting technique
- scientific article; zbMATH DE number 1839432 (Why is no real title available?)
- Space-bounded quantum complexity
- Developments in Language Theory
- scientific article; zbMATH DE number 6004860 (Why is no real title available?)
- Computing Boolean functions via quantum hashing
- Quantum versus classical online streaming algorithms with logarithmic size of memory
- Quantum online algorithms with respect to space and advice complexity
- On the average sensitivity of the weighted sum function
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Two-way and one-way quantum and classical automata with advice for online minimization problems
This page was built for publication: Quantum branching programs and space-bounded nonuniform quantum complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1779302)
