Characterization of quantum computable decision problems by state discrimination

Abstract

One advantage of quantum algorithms over classical computation is the possibility to spread out, process, analyse and extract information in multipartite configurations in coherent superpositions of classical states. This will be discussed in terms of quantum state identification problems based on a proper partitioning of mutually orthogonal sets of states. The question arises whether or not it is possible to encode equibalanced decision problems into quantum systems, so that a single invocation of a filter used for state discrimination suffices to obtain the result.

9 pages

References in corpus (3)

• An Introduction to Quantum Complexity Theory
• A polynomial-time solution to the parity problem on an NMR quantum computer
• Maximum predictive power and the superposition principle

Cited by in corpus (5)

• Generalized Greenberger-Horne-Zeilinger arguments from quantum logical analysis
• On the solution of trivalent decision problems by quantum state identification
• Quantum advantage by relational queries about physically realizable equivalence classes
• Physics and metaphysics looks at computation
• Quantum-like Description of Probabilistic Data from Shafir-Tversky Experiments: evidence of trigonometric and hyperbolic (!) interference