Classical and Quantum Algorithms for USO Recognition Article Swipe

PDF

Related Concepts

Oracle Computer science Quantum computer Computation Theoretical computer science Quantum Combinatorial algorithms Algorithm Programming language Physics Quantum mechanics

Vitor Bosshard ·

YOU? · · 2015 · Open Access · · DOI: https://doi.org/10.3929/ethz-a-010540777 · OA: W2285539899

Unique Sink Orientations (USOs) are orientations of the hypercube graph capable of encoding many optimization problems, such as linear programming. When a USO is given in implicit form as an oracle, the USO recognition problem aims to distinguish USO from non-USO oracles. In this thesis we introduce a new type of orientation, the pseudo-USOs, which are closely related to the USO recognition problem. We derive many of their combinatorial properties, up to and including a full characterization. Using these properties, we design efficient USO recognition algorithms both in the classical and quantum models of computation.