We explore finite-field frameworks for quantum theory and quantum computation. The simplest theory, defined over unrestricted finite fields, is unnaturally strong. A second framework employs only finite fields with no solution to x^2+1=0, and thus permits an elegant complex representation of the extended field by adjoining i=\sqrt{-1}. Quantum theories over these fields recover much of the structure of conventional quantum theory except for the condition that vanishing inner products arise only from null states; unnaturally strong computational power may still occur. Finally, we are led to consider one more framework, with further restrictions on the finite fields, that recovers a local transitive order and a locally-consistent notion of inner product with a new notion of cardinal probability. In this framework, conventional quantum mechanics and quantum computation emerge locally (though not globally) as the size of the underlying field increases. Interestingly, the framework allows one to choose separate finite fields for system description and for measurement: the size of the first field quantifies the resources needed to describe the system and the size of the second quantifies the resources used by the observer. This resource-based perspective potentially provides insights into quantitative measures for actual computational power, the complexity of quantum system definition and evolution, and the independent question of the cost of the measurement process.
We explore finite-field frameworks for quantum theory and quantum computation. The simplest theory, defined over unrestricted finite fields, is unnaturally strong. A second framework employs only finite fields with no solution to x^2+1=0, and thus permits an elegant complex representation of the extended field by adjoining i=\sqrt{-1}. Quantum theories over these fields recover much of the structure of conventional quantum theory except for the condition that vanishing inner products arise only from null states; unnaturally strong computational power may still occur. Finally, we are led to consider one more framework, with further restrictions on the finite fields, that recovers a local transitive order and a locally-consistent notion of inner product with a new notion of cardinal probability. In this framework, conventional quantum mechanics and quantum computation emerge locally (though not globally) as the size of the underlying field increases. Interestingly, the framework allows one to choose separate finite fields for system description and for measurement: the size of the first field quantifies the resources needed to describe the system and the size of the second quantifies the resources used by the observer. This resource-based perspective potentially provides insights into quantitative measures for actual computational power, the complexity of quantum system definition and evolution, and the independent question of the cost of the measurement process.
We explore the implications of restricting the framework of quantum theory and quantum computation to finite fields. The simplest proposed theory is defined over arbitrary finite fields and loses the notion of unitaries. This makes such theories unnaturally strong, permitting the search of unstructured databases faster than asymptotically possible in conventional quantum computing. The next most general approach chooses finite fields with no solution to x^2+1=0, and thus permits an elegant complex-like representation of the extended field by adjoining i=sqrt(-1). Quantum theories over these fields retain the notion of unitaries and --- for particular problem sizes --- allow the same algorithms as conventional quantum theory. These theories, however, still support unnaturally strong computations for certain problem sizes, but the possibility of such phenomena decreases as the size of the field increases.
In recent work, Benjamin Schumacher and Michael~D. Westmoreland investigate a version of quantum mechanics which they call "modal quantum theory" but which we prefer to call "discrete quantum theory". This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, discrete quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. Our first result is to distill a model of discrete quantum computing from this quantum theory. The model is expressed using a monadic metalanguage built on top of a universal reversible language for finite computations, and hence is directly implementable in a language like Haskell. In addition to superpositions and invertible linear maps, the model includes conventional programming constructs including pairs, sums, higher-order functions, and recursion. Our second result is to relate this programming model to relational programming, e.g., a pure version of Prolog over finite relations. Surprisingly discrete quantum computing is identical to conventional logic programming except for a small twist that is responsible for all the ``quantum-ness.'' The twist occurs when merging sets of answers computed by several alternatives: the answers are combined using an "exclusive" version of logical disjunction. In other words, the two branches of a choice junction exhibit an "interference" effect: an answer is produced from the junction if it occurs in one or the other branch but not both.
Quantum physics currently provides our deepest description of nature. To understand precisely how it differs from classical physics is not only of foundational interest, but also important to advance technology: the advent of quantum information has led to the insight that certain quantum phenomena, e.g., entanglement and coherence, are resources which enable us to solve practical tasks that are unsolvable within the realm of classical physics. But how can we quantify quantum resources and how do we decide which resource is relevant for a specific operational advantage in quantum cryptography, quantum computation, or quantum metrology? How can we employ these resources optimally? Addressing these questions is the motivation for the development of quantum resource theories, a mathematically rigorous framework that allows us to investigate a specific quantum phenomenon as a resource. Formally, such theories emerge from restrictions which are imposed in addition to the laws of quantum mechanics. A prominent example is the restriction to local operations and classical communication, which singles out entanglement as a resource. Typically, such theories describe the value of quantum states, i.e., static resources. An important question in such theories concerns their structure as determined by the restriction under consideration, which is analyzed for coherence theory on qubits in this thesis. Only recently, so-called dynamical resource theories that quantify the value of operations were proposed, which are advantageous for several reasons: they include resource theories of states as special cases, allow us to quantify additional quantum properties such as the detection or usage of static resources, which will be a main topic of this thesis, and are more natural from an operational perspective. But are different types of dynamical resources present in quantum operations related? For the case of dynamical coherence and entanglement, it will be shown that there is not only a quantitative, but also a qualitative connection.
Conventional quantum computing entails a geometry based on the description of an n-qubit state using 2^{n} infinite precision complex numbers denoting a vector in a Hilbert space. Such numbers are in general uncomputable using any real-world resources, and, if we have the idea of physical law as some kind of computational algorithm of the universe, we would be compelled to alter our descriptions of physics to be consistent with computable numbers. Our purpose here is to examine the geometric implications of using finite fields Fp and finite complexified fields Fp^2 (based on primes p congruent to 3 mod{4}) as the basis for computations in a theory of discrete quantum computing, which would therefore become a computable theory. Because the states of a discrete n-qubit system are in principle enumerable, we are able to determine the proportions of entangled and unentangled states. In particular, we extend the Hopf fibration that defines the irreducible state space of conventional continuous n-qubit theories (which is the complex projective space CP{2^{n}-1}) to an analogous discrete geometry in which the Hopf circle for any n is found to be a discrete set of p+1 points. The tally of unit-length n-qubit states is given, and reduced via the generalized Hopf fibration to DCP{2^{n}-1}, the discrete analog of the complex projective space, which has p^{2^{n}-1} (p-1)\prod_{k=1}^{n-1} (p^{2^{k}}+1) irreducible states. Using a measure of entanglement, the purity, we explore the entanglement features of discrete quantum states and find that the n-qubit states based on the complexified field Fp^2 have p^{n} (p-1)^{n} unentangled states (the product of the tally for a single qubit) with purity 1, and they have p^{n+1}(p-1)(p+1)^{n-1} maximally entangled states with purity zero.
Abstract. Conventional quantum computing entails a geometry based on the description of an n-qubit state using 2n infinite precision complex numbers denoting a vector in a Hilbert space. Such numbers are in general uncomputable using any real-world resources, and, if we have the idea of physical law as some kind of computational algorithm of the universe, we would be compelled to alter our descriptions of physics to be consistent with computable numbers. Our purpose here is to examine the geometric implications of using finite fields Fp and finite complexified fields Fp2 (based on primes p congruent to 3 (mod 4)) as the basis for computations in a theory of discrete quantum computing, which would therefore become a computable theory. Because the states of a discrete n-qubit system are in principle enumerable, we are able to determine the proportions of entangled and unentangled states. In particular, we extend the Hopf fibration that defines the irreducible state space of conventional continuous n-qubit theories (which is the complex projective space CP2 n−1) to an analogous discrete geometry in which the Hopf circle for any n is found to be a discrete set of p+1 points. The tally of unit-length n-qubit states is given, and reduced via the generalized Hopf fibration to DCP2 n−1, the discrete analog of the complex projective space, which has p2 n−1(p − 1) ∏n−1k=1(p2k + 1) irreducible states. Using a measure of entanglement, the purity, we explore the entanglement features of discrete quantum states and find that the n-qubit states based on the complexified field Fp2 have p n(p − 1)n unentangled states (the product of the tally for a single qubit) with purity 1, and they have pn+1(p − 1)(p+ 1)n−1 maximally entangled states with purity zero.
From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that , where is a classical complexity class (known to be included in , hence ). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterized by local measurements), efficient computations are contained in . This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, , is equal to . Given only the assumption of tomographic locality, the inclusion in still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativized complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a 'classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include .