Research On Algorithm And Complexity Of Quantum Information And Computational Economics

Quantum information and Computational economics are two newlyfocused points in theoretical computer science, which involve problems suchas quantum states discrimination, quantum entanglement, Nash equilibriumprices, and combinatorial auctions etc., which have profound meaning intheory as well as in practice.In this paper we studied the following five problems:1. We investigate the lower bound of quantum query complexity forgraph properties, cyclic functions, and symmetric functions. Weshow that their quantum complexity is at least ? ( N^1/4). Furthermore,for Scorpion graph property and another cyclic function, we give twoO ( N^1/4) time quantum algorithm. So the lower bound is tight.2. With the catalyst quantum entanglement states' help, we cantransform one entanglement state into another by local quantumoperation and classical communication (LOCC). We show thenecessary and sufficient condition for the existence of 2× 2 catalystfor two 4× 4 states. We also give a polynomial time algorithm forgeneral k × k catalyst states.3. We show that the problem of success probability of unambiguousdiscrimination is equivalent to a semi-definite programming (SDP)problem. We also give a family of lower bounds for the optimaldiscrimination probability.4. We study efficient algorithms for computing equilibrium price in theFisher model for a class of nonlinear concave utility functions, thelogarithmic utility functions. We derive a duality relation betweenbuyers and sellers under such utility functions, and use it to design apolynomial time algorithm for calculating equilibrium price.5. We consider complexity issues for a special type of combinatorialauctions, the single-minded auction, where every agent is interestedin only one subset of the commodities. We present a match bound onthe communication complexity for single-minded auction. We proveit is NP-hard to decide whether Walrasian equilibrium exists insingle-minded action. And we establish a polynomial size dualitytheorem for the existence of Walrasian equilibrium.