Abstract A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a computation that is impossible for classical computers. Existing approaches to provide proofs of quantumness depend on unproven assumptions about some task being impossible for machines of a particular model under certain resource restrictions. We study a setup where both devices have space bounds o (log log n ). Under such memory budgets, it has been unconditionally proven that probabilistic Turing machines are unable to solve certain computational problems. We formulate a new class of problems and show that these problems are polynomial-time solvable for quantum machines, impossible for classical machines, and have the property that their solutions can be “proved” by a small-space quantum machine to a classical machine with the same space bound. These problems form the basis of our newly defined protocol, where the polynomial-time verifier's verdict about the tested machine's quantumness is not conditional on an unproven weakness assumption.
Abstract A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a computation that is impossible for classical computers. Existing approaches to provide proofs of quantumness depend on unproven assumptions about some task being impossible for machines of a particular model under certain resource restrictions. We study a setup where both devices have space bounds o (log log n ). Under such memory budgets, it has been unconditionally proven that probabilistic Turing machines are unable to solve certain computational problems. We formulate a new class of problems and show that these problems are polynomial-time solvable for quantum machines, impossible for classical machines, and have the property that their solutions can be “proved” by a small-space quantum machine to a classical machine with the same space bound. These problems form the basis of our newly defined protocol, where the polynomial-time verifier's verdict about the tested machine's quantumness is not conditional on an unproven weakness assumption.
This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.
The promise of scalable quantum technology appears more realistic, after recent advances in both theory and experiment. Assuming a quantum computer is developed, the task of verifying the correctness of its outcome becomes crucial. Unfortunately, for a system that involves many particles, predicting its evolution via classical simulation becomes intractable. Moreover, verification of the outcome by computational methods, i.e. involving a classical witness, is believed inefficient for the hardest problems solvable by a quantum computer. A feasible alternative to verify quantum computation is via cryptographic methods, where an untrusted prover has to convince a weak verifier for the correctness of his outcome. This is the approach we take in this thesis. In the most standard configuration the prover is capable of computing all polynomial-time quantum circuits and the verifier is restricted to classical with very modest quantum power. The goal of existing verification protocols is to reduce the quantum requirements for the verifier - ideally making it purely classical - and reduce the communication complexity. In Part II we propose a composition of two existing verification protocols [Fitzsimons and Kashefi, 2012], [Aharonov et al., 2010] that achieves quadratic improvement in communication complexity, while keeping the quantum requirements for the verifier modest. Along this result, several new techniques are proposed, including the generalization of [Fitzsimons and Kashefi, 2012] to prime dimensions. In Part III we discuss the idea of model-specific quantum verification, where the prover is restricted to intermediate quantum power, i.e. between full-fledged quantum and purely classical, thus more feasible experimentally. As a proof of principle we propose a verification protocol for the One-Pure-Qubit computer [Knill and Laflamme, 1998], which tolerates noise and is capable of computing hard problems such as large matrix trace estimation. The verification protocol is an adaptation of [Fitzsimons and Kashefi, 2012] running on Measurement-Based Quantum Computing with newly proved properties of the underlying resources. Connections of quantum verification to other security primitives are considered in Part IV. Authenticated quantum communication has been already proved to relate to quantum verification. We expand this by proposing a quantum authentication protocol derived from [Fitzsimons and Kashefi, 2012] and discuss implications to verification with purely classical verifier. Connections between quantum security primitives, namely blindness - prover does not learn the computation -, and classical security are considered in Part V. We introduce a protocol where a client with restricted classical resources computes blindly a universal classical gate with the help of an untrusted server, by adding modest quantum capabilities to both client and server. This example of quantum-enhanced classical security we prove to be a task classically impossible.
In this dissertation, we investigate the computational power of quantum Turing machines operating in bounded space. First, we consider space-bounds that are space-constructible and at least logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.
Demonstrating that a machine performs genuinely quantum operations is a central challenge in quantum information processing. Existing proofs of quantumness typically rely on computational tasks that are infeasible for classical machines under assumptions such as computational hardness, or explicit bounds on classical runtime, memory, or oracle queries. Here we introduce an alternative paradigm: a thermodynamic proof of quantumness based on energy consumption. Using the search problem of Yamakawa and Zhandry with a structureless uniformly random oracle, we show that any classical machine solving the task with constant success probability must generate entropy that grows exponentially with the security parameter. By Landauer's principle, this implies an exponential lower bound on heat dissipation and hence on the energy consumption of any cyclic classical implementation. In contrast, the corresponding quantum prover solves the task with polynomial query and gate complexity, giving polynomial energy consumption under standard assumptions for quantum implementations. Thus, in the random-oracle setting, sufficiently low energy consumption in a successful implementation certifies quantumness through a macroscopic thermodynamic observation of energy consumption.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.