本論文研究兩個有關量子計算理論中的問題，其一為量子博弈論，其二為量子查詢複雜度。 / 博弈論於經濟學、計算機科學、生物學、數學等領域中皆為一門重要課題，近年越來越多有關的研究都把焦點放於量子博弈論之上。本論文的第一部份，我們研究由張氏於2010 年提出的量子策略博弈模型。其中研究重點在於某特定類型的博弈中，計算使用量子策略比經典策略多出的優勢。我們成功建構出一個特定的博弈，並証明使用量子策略比經典策略多出的優勢跟策略的多少成線性關係。 / 本論文的第二部份，主要研究有關量子查詢複雜度，它提供一個簡單的框架，用於理解量子力學的計算能力和限制。我們研究的重點在於量子的安得拉-卡普-羅森伯格猜想，那是關於決定某一類圖特性所需的量子查詢複雜度。我們將會介紹施氏與張氏的猜想、布爾函數分析及查詢複雜度研究中重要的研究結果。我們嘗試証明施氏與張氏的猜想，並於最後提出一個有關布爾函數塊敏感度，影響度及方差值的猜想。 / We study two problems, one in quantum game theory and another in quantum query complexity. / Game theory is an important research topic in many elds like economics, computer sciences, biology, mathematics, etc. A growing trend is that game theory is being studied under quantum setting. In part I, we study the quantum strategic game model proposed by Zhang [Zha10], in which one of the main problem is to measure quantitatively the advantages of using quantum strategies over classical ones. A natural measure is the increase of payoff , which is quantified in terms of multiplicative incentive in a normalized n x n bimatrix game. The maximal incentive under superposition mapping, which maps a classical correlated equilibrium p to a quantum state Σ[subscript s] Pspp(s) jsi, is conjectured to be Ω(n). However only a correlated equilibrium with multiplicative incentive n°·⁵⁸⁵··· under such mapping was found. We proved this conjecture by constructing a classical correlated equilibrium with multiplicative incentive of (n+3)/4 =Ω(n) under such mapping. The proof is much simpler than the old one and gives an optimal result. / On the other hand, we studied quantum query complexity, which provides a simple framework for understanding the computational power and limit by quantum mechanics. In particular, we are interested in the quantum version of Aanderaa-Karp-Rosenberg conjecture for non-trivial monotone graph properties. In part II, we introduce the conjecture by Shi and Zhang [SZ05], survey some important results in Boolean function analysis and query complexity. We put down some partial results on resolving conjecture of Shi and Zhang and propose another conjecture regarding block sensitivity, in uence and variance of a Boolean function, which is simple, interesting and related to the problem. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Wong, Chung Hoi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves [89]-94). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter I --- Quantum Strategic Game --- p.1 / Chapter 1 --- Classical and Quantum Strategic Game --- p.5 / Chapter 1.1 --- Classical Strategic Game Theory --- p.6 / Chapter 1.1.1 --- Notation for Strategic Game --- p.6 / Chapter 1.1.2 --- Classical Equilibrium --- p.7 / Chapter 1.2 --- Quantum Strategic Game Theory --- p.9 / Chapter 1.2.1 --- Notation for Quantum Strategic Game --- p.9 / Chapter 1.2.2 --- Quantum Equilibrium --- p.11 / Chapter 1.3 --- Preservation of Equilibrium --- p.11 / Chapter 1.3.1 --- Quantum to Classical --- p.12 / Chapter 1.3.2 --- Classical to Quantum --- p.12 / Chapter 2 --- Incentives in Quantum Strategic Game --- p.15 / Chapter 2.1 --- Previous Result --- p.15 / Chapter 2.2 --- Improved Multiplicative Incentive to n0:638 --- p.17 / Chapter 2.3 --- Improved Multiplicative Incentives to (n) --- p.19 / Chapter II --- Quantum Aanderaa-Karp-Rosenberg Conjecture --- p.23 / Chapter 3 --- Introduction --- p.27 / Chapter 3.1 --- Non-Trivial Monotone Graph Properties --- p.27 / Chapter 3.2 --- Aanderaa-Karp-Rosenberg Conjecture --- p.27 / Chapter 3.3 --- Conjecture of Shi and Zhang --- p.28 / Chapter 4 --- Boolean Function Analysis --- p.31 / Chapter 4.1 --- Notations --- p.31 / Chapter 4.1.1 --- Sensitivity and Block Sensitivity --- p.32 / Chapter 4.1.2 --- p-biased Mean and Variance --- p.33 / Chapter 4.1.3 --- p-biased Influence --- p.34 / Chapter 4.2 --- p-biased Fourier Analysis --- p.36 / Chapter 5 --- Decision Tree Complexity --- p.43 / Chapter 5.1 --- Deterministic Decision Tree Complexity --- p.43 / Chapter 5.2 --- Randomized Decision Tree Complexity --- p.45 / Chapter 5.3 --- Non-Deterministic Decision Tree Complexity --- p.47 / Chapter 5.4 --- Quantum Query Complexity --- p.50 / Chapter 5.5 --- The General Adversary Bound --- p.52 / Chapter 5.6 --- Quantum Query Complexity Lower Bound --- p.54 / Chapter 6 --- Classes of Boolean Function and Their Properties --- p.59 / Chapter 6.1 --- Properties of Monotone Functions --- p.59 / Chapter 6.2 --- Properties of Transitive Functions --- p.64 / Chapter 6.3 --- Properties of Monotone and Transitive Function --- p.70 / Chapter 7 --- Conjecture of Shi and Zhang --- p.73 / Chapter 7.1 --- Designing the Adversary Matrix by Fourier Coefficients of the Weight Function --- p.73 / Chapter 7.2 --- Designing of Adversary Matrix by Level k Fourier Weight --- p.78 / Chapter 8 --- Block Sensitivity-Influence Conjecture --- p.81 / Chapter 8.1 --- Boolean Functions That Satisfy the BSI Conjecture --- p.83 / Chapter 8.2 --- Recursive k-Majority --- p.84 / Chapter 8.3 --- Tribes of Size k --- p.85 / Chapter 8.4 --- Boolean Functions with Small Sensitivity Are Sparse --- p.87 / Bibliography --- p.89
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_327974 |
| Date | January 2012 |
| Contributors | Wong, Chung Hoi., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (viii, 94 leaves) : ill. |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0021 seconds