Michele Mosca

TCS Journal 2014 Journal Article

Public-key cryptography based on bounded quantum reference frames

• Lawrence M. Ioannou
• Michele Mosca

We demonstrate that the framework of bounded quantum reference frames has application to building quantum-public-key cryptographic protocols and proving their security. Thus, the framework we introduce can be seen as a public-key analogue of the framework of Bartlett et al. [1], where a private shared reference frame is shown to have cryptographic application. The protocol we present in this paper is an identification scheme, which, like a digital signature scheme, is a type of authentication scheme. We prove that our protocol is both reusable and secure under the honest-verifier assumption. Thus, we also demonstrate that secure reusable quantum-public-key authentication is possible to some extent.

STOC Conference 2009 Conference Paper

Efficient discrete-time simulations of continuous-time quantum query algorithms

• Richard Cleve
• Daniel Gottesman
• Michele Mosca
• Rolando D. Somma
• David L. Yonge-Mallo

The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. We show that any quantum algorithm in this model whose total query time is T can be simulated by a quantum algorithm in the discrete-time query model that makes O(T log T / loglog T) subset O~(T) queries. This is the first such upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Omega(T loglog T / log T) subset Omega~(T) in the continuous-time query model.

TCS Journal 2001 Journal Article

Counting by quantum eigenvalue estimation

• Michele Mosca

For every “computation” there corresponds the physical task of manipulating a starting state into an output state with a desired property. As the classical theory of physics has been replaced by quantum physics, it is interesting to consider the capabilities of a computer that can exploit the distinctive quantum features of nature. The extra capabilities seem enormous. For example, with only an expected O( N ) evaluations of a function f: {0, 1, …, N−1}→{0, 1}, we can find a solution to f(x)=1 provided one exists. Another example is the ability to find efficiently the order of an element g in a group by using a quantum computer to estimate a random eigenvalue of the unitary operator that multiplies by g in the group. By using this eigenvalue estimation algorithm to estimate an eigenvalue of the unitary operator used in quantum searching we can approximately count the number of solutions to f(x)=1. This paper describes this eigenvector approach to quantum counting and related algorithms.

FOCS Conference 2001 Conference Paper

How Powerful is Adiabatic Quantum Computation?

• Wim van Dam
• Michele Mosca
• Umesh V. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

FOCS Conference 2000 Conference Paper

Private Quantum Channels

• Andris Ambainis
• Michele Mosca
• Alain Tapp
• Ronald de Wolf

We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular, we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme.

STOC Conference 2000 Conference Paper

Self-testing of universal and fault-tolerant sets of quantum gates

• Wim van Dam
• Frédéric Magniez
• Michele Mosca
• Miklos Santha

FOCS Conference 1998 Conference Paper

Quantum Lower Bounds by Polynomials

• Robert Beals
• Harry Buhrman
• Richard Cleve
• Michele Mosca
• Ronald de Wolf

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0, 1}/sup N/ in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i. e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T/sup 6/) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.