Quantum Branching Programs and Space-Bounded Nonuniform Quantum Complexity

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.

45 pages, 3 Postscript figures. Proofs rearranged, typos corrected

References in corpus (3)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Efficient Discrete Approximations of Quantum Gates
• Quantum and Stochastic Branching Programs of Bounded Width

Cited by in corpus (9)

• Algorithms for Quantum Branching Programs Based on Fingerprinting
• Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
• Space Complexity of Streaming Algorithms on Universal Quantum Computers
• On Computational Power of Quantum Read-Once Branching Programs
• Quantum vs. Classical Read-once Branching Programs
• Quantum Ordered Binary Decision Diagrams with Repeated Tests
• Nondeterministic unitary OBDDs
• The Minimal and Maximal Sensitivity of the Simplified Weighted Sum Function
• The simplified weighted sum function and its average sensitivity