摘要: Unique Sink Orientations (USOs) are orientations of the hypercube graph capable encoding many optimization problems, such as linear programming. When a USO is given in implicit form an oracle, recognition problem aims to distinguish from non-USO oracles. In this thesis we introduce new type orientation, pseudo-USOs, which closely related problem. We derive their combinatorial properties, up and including full characterization. Using these design efficient algorithms both classical quantum models computation.
sci-hub.st 参考文章(24)
Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach Cambridge University Press. ,(2009) , 10.1017/CBO9780511804090
Oded Goldreich, On Promise Problems: A Survey Lecture Notes in Computer Science. pp. 254- 290 ,(2006) , 10.1007/11685654_12
M. Szegedy, Quantum speed-up of Markov chain based algorithms foundations of computer science. pp. 32- 41 ,(2004) , 10.1109/FOCS.2004.53
Andrew M. Childs, Jason M. Eisenberg, Quantum algorithms for subset finding Quantum Information & Computation. ,vol. 5, pp. 593- 604 ,(2005) , 10.5555/2011656.2011663
Ingo Schurr, Bernd Gärtner, Linear programming and unique sink orientations symposium on discrete algorithms. pp. 749- 757 ,(2006) , 10.5555/1109557.1109639
Walter D. Morris jr., Randomized pivot algorithms for P-matrix linear complementarity problems Mathematical Programming. ,vol. 92, pp. 285- 296 ,(2002) , 10.1007/S101070100268
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha, Search via Quantum Walk SIAM Journal on Computing. ,vol. 40, pp. 142- 164 ,(2011) , 10.1137/090745854
Tibor Szab�, Ingo Schurr, Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes Discrete and Computational Geometry. ,vol. 31, pp. 627- 642 ,(2004) , 10.1007/S00454-003-0813-8
Eli Biham, Gilles Brassard, Dan Kenigsberg, Tal Mor, Quantum computing without entanglement Theoretical Computer Science. ,vol. 320, pp. 15- 33 ,(2004) , 10.1016/J.TCS.2004.03.041
Scott Aaronson, Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems Journal of the ACM. ,vol. 51, pp. 595- 605 ,(2004) , 10.1145/1008731.1008735