本論文研究兩個有關量子計算理論中的問題，其一為量子博弈論，其二為量子查詢複雜度。 / 博弈論於經濟學、計算機科學、生物學、數學等領域中皆為一門重要課題，近年越來越多有關的研究都把焦點放於量子博弈論之上。本論文的第一部份，我們研究由張氏於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

Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.

Chang, Kwong Wa = 一般量子系統非馬可夫領域的主方程 / 張光華. / "October 2010." / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 89-92). / Abstracts in English and Chinese. / Chang, Kwong Wa = Yi ban liang zi xi tong fei Makefu ling yu de zhu fang cheng / Zhang Guanghua. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Born-Markov Master Equations --- p.4 / Chapter 2.1 --- Master Equations from von Neumann equation --- p.4 / Chapter 2.2 --- Born Approximation --- p.6 / Chapter 2.3 --- Markov Approximation --- p.8 / Chapter 2.4 --- Born-Markov Approximation --- p.10 / Chapter 2.5 --- Lindblad Equation --- p.12 / Chapter 2.6 --- The Limitations of the Born-Markov Approximation --- p.16 / Chapter 2.7 --- Beyond Born and Markov Approximations --- p.20 / Chapter 2.7.1 --- General projection operator approach --- p.20 / Chapter 2.7.2 --- Time-local form of the master equation --- p.21 / Chapter 3 --- TCL non-Markovian Master Equation for Linear Systems --- p.24 / Chapter 3.1 --- Model --- p.24 / Chapter 3.2 --- The General Structure of the TCL non-Markovian Master Equation for Initially Factorizable States --- p.27 / Chapter 3.3 --- Determination of Unknown Coefficients --- p.32 / Chapter 3.4 --- Weak-Coupling Approximation --- p.46 / Chapter 3.5 --- Steady State Solutions --- p.51 / Chapter 4 --- An Application: Coherence Protection by Parity Kicks --- p.54 / Chapter 4.1 --- Review on Parity Kicks --- p.54 / Chapter 4.2 --- Parity Kicks oil Damped Harmonic Oscillators --- p.58 / Chapter 4.3 --- Numerical Results for Soft Pulses --- p.61 / Chapter 5 --- Other Initial States --- p.67 / Chapter 5.1 --- Factorizable States --- p.67 / Chapter 5.2 --- Non-Factorizable States --- p.73 / Chapter 6 --- Non-Markovianity --- p.75 / Chapter 6.1 --- The Concept of non-Markovianity --- p.75 / Chapter 6.2 --- A Recent Measure --- p.76 / Chapter 6.3 --- A Prospective Measure --- p.79 / Chapter 7 --- Conclusion --- p.87 / Bibliography --- p.89 / Chapter A --- Evolution of Factorizable Coherent State for Linear Damped Harmonic Oscillator with RWA --- p.93 / Chapter B --- "Derivation of G, L and F" --- p.95 / Chapter C --- Comparison of Equations of Motion for Master Equation Coefficients --- p.98

Adopting the continuous frequency mode approach and the resolvent method, we study the interaction between atoms and photons in leaky optical cavities. In particular, we highlight the physical significance of quantum states of photons in such processes. Single-photon processes and two-photon processes are intensively investigated. With single-photon scattering, various schemes for generating entangled pairs and constructing quantum gates are developed using two-level atoms or Λ-type atoms. The fidelities of these schemes tend to unity for injected photons with specific spectra. We examine the efficiency of the feedback scheme proposed by Hong and Lee [Phys. Rev. Lett. 89 , 237901 (2002)] to generate maximally entangled states of two atoms in an optical cavity from first principles. We find that the efficiency of the scheme deteriorates gradually and hence other competing processes have to be considered properly. Besides, nonlinearity and entanglement of two-photon states in two-sided and one-sided cavities are analyzed in terms of detection probabilities and frequency-correlation of the left- and right-output photons. We discover that two-photon processes in a one-sided cavity can be exploited to generate two-photon maximally entangled states, from which nonlocal shaping effect in the spectra of the two photons can be demonstrated. Lastly, based on the Fredholm method, an iterative analytical method yielding the Schmidt modes and eigenvalues of an entangled state is proposed and discussed. / Fung, Ho Tak = 光子與原子在漏空腔中的糾纏及其在量子計算中的應用 / 馮浩德. / "May 2008." / Adviser: P. T. Leung. / Source: Dissertation Abstracts International, Volume: 70-03, Section: B, page: 1736. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (p. 155-163). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307. / Fung, Ho Tak = Guang zi yu yuan zi zai lou kong qiang zhong de jiu chan ji qi zai liang zi ji suan zhong de ying yong / Feng Haode.

The renormalisation group is a crucial tool for understanding scale-dependent quantum field theories. Renormalisation group fixed points correspond to theories where scale invariance is restored at the quantum level, and may provide high- or low-energy limits for more general quantum field theories. In particular, those reached in the ultraviolet allow theories to be defined microscopically, a scenario known as asymptotic safety. In this work I investigate fixed points of conventional four-dimensional, at-space, perturbatively renormalisable, local quantum field theories. Focusing on weakly interacting fixed points the problem becomes amenable to perturbation theory. The approach is twofold: on the one hand to understand general conditions for the existence of such fixed points, and on the other to construct theories which introduce new features compared to previous examples. To understand perturbative fixed points, general calculations for theories of this type are exploited. It is established, for gauge theories, interacting fixed points may be nonzero in gauge couplings alone, or in gauge and Yukawa couplings. Deriving novel group theory bounds it is established that only the latter may possibly be ultraviolet. Additionally it is shown that theories without gauge interactions cannot possess weakly coupled fixed points, and the connexion between this fact and the impossibility of such theories being asymptotically free is highlighted. Two explicit families of examples are presented: a theory with semisimple gauge group is analysed in detail, containing many new fixed points, a rich phase structure, and asymptotically safe regions of parameter space, and a separate supersymmetric model with an ultraviolet fixed point, providing the first known explicit example of an asymptotically safe supersymmetric gauge theory.

Since the beginning of the 20th century, much time and effort has been invested in the search for a theory of quantum gravity. While this provided a myriad of possibilities, it has so far failed to find a definitive answer. Here we take an alternative approach: instead of constructing a theory of quantum gravity and examining its low energy limit, we start with the conventional theory and ask what are the first deviations induced by a possible quantization of gravity. It is proposed that in this limit quantum gravity, whatever the ultimate theory might be, manifests itself as non-locality. In this thesis are explored two different approaches to effective theories. In the first, it is demonstrated how combining quantum field theory with general relativity naturally gives rise to non-locality. This is explored in the context of inflation, a natural place to look for high energy phenomena. By considering a simple scalar field theory, it is shown how non-locality results in higher dimensional operators and what the effects are on inflationary models. The second approach looks at a theory which naturally incorporates a minimal scale. Noncommutative geometry parallels the phase space or deformation quantization approach of quantum mechanics. It supposes that at short scales, the structure of spacetime is algebraic rather than geometric. In the first instance, we follow the first section and look at cosmological implications by replacing normal scalar theory with its noncommutative counterpart. In the second, we take a step back and examine the implications of quantization on the differential geometry. The formalism is developed and applied to generic spherically symmetric spacetimes where it is shown that to first order in deformation, the quantization is unique.

Decoherence and errors appear among the main challenges to implement successful quantum technologies. In this thesis I discuss the application of some general tools and principles that may be valuable resources to develop robust technologies, with applications in quantum sensing and quantum simulation. Firstly, we employ suitable periodically driving fields acting on the Ising model in order to tailor spin-spin interactions depending on the spatial direction of the bonds. In this way, we are able to simulate the quantum compass model on a square lattice. This system exhibits topological order and a doubly degenerate ground state protected against local noise. A possible implementation of this proposal is outlined for atomic quantum simulators. Secondly, we exploit two general working principles based on spontaneous symmetry breaking and criticality that may be beneficial to achieve robust quantum sensors, particularly appropriate for quantum optical dissipative systems. A concrete application is given for a minimal model: a single qubit laser. It is shown how the precision in parameter estimation is enhanced as the incoherent pumping acting on the qubit increases, and also when the system is close to the lasing critical point. Finally, classical long-range correlations in lattice systems are shown to provide us with an additional resource to be used in robust sensing schemes. The previous setup is extended to a lattice of single qubit lasers where interactions are incoherent. Under the right conditions, we show that a Heisenberg scaling with the number of probes can be accomplished.

This dissertation explores two topics located in the intersection of quantum mechanics and cosmology. Entanglement harvesting is a phenomenon in which quantum entanglement can develop between the states of two Unruh-DeWitt detectors travelling through spacetime by way of mutual interaction with a scalar quantum field. I numerically explore entanglement harvesting of Unruh-DeWitt detectors in Minkowski space travelling with constant acceleration, generalizing previous analytical results which held only in a limiting case. Cosmic bubble collisions arise in inflationary cosmology as a mechanism to begin reheating at the end of inflation. I extend the previously proposed theory of boom and bust inflation which relies on the existence of a large extra dimension by exploring particular inflationary models in which reheating need not begin the first time that two bubble walls collide. This allows for a smaller lower bound on the size of the compact extra dimension in the boom and bust proposal.

We study the propagation of waves in spatially non-homogeneous media focusing on Schrodinger’s equation of quantum mechanics and Maxwell’s equations of electromagnetism. We assume that medium variation occurs over two distinct length scales: a short ‘fast’ scale with respect to which the variation is periodic, and a long ‘slow’ scale over which the variation is smooth. Let epsilon denote the ratio of these scales. We focus primarily on the time evolution of asymptotic solutions (as epsilon tends to zero) known as semiclassical wavepackets. Such solutions generalize exact time-dependent Gaussian solutions and ideas of Heller and Hagedorn to periodic media. Our results are as follows: 1) To leading order in epsilon and up to the ‘Ehrenfest’ time-scale t ~ log 1/epsilon, the center of mass and average (quasi-)momentum of the semiclassical wavepacket satisfy the equations of motion of the classical Hamiltonian given by the wavepacket’s Bloch band energy. Our first result is to derive all corrections to these dynamics proportional to epsilon. These corrections consist of terms proportional to the Bloch band’s Berry curvature and terms which describe coupling to the evolution of the wavepacket envelope. These results rely on the assumption that the wavepacket’s Bloch band energy is non-degenerate. 2) We then consider the case where, in one spatial dimension, a semiclassical wavepacket is incident on a Bloch band crossing, a point in phase space where the wavepacket’s Bloch band energy is degenerate. By a rigorous matched asymptotic analysis, we show that at the time the wavepacket meets the crossing point a second wavepacket, associated with the other Bloch band involved in the crossing, is excited. Our result can be seen as a rigorous justification of the Landau-Zener formula in this setting. 3) Our final result generalizes the recent work of Fefferman, Lee-Thorp, and Weinstein on one-dimensional ‘edge’ states. We characterize the bound states of a Schrodinger operator with a periodic potential perturbed by multiple well-separated domain wall ‘edge’ modulations, by proving a theorem on the near zero eigenstates of an emergent Dirac operator.

Abstract not available