Joseph F. Fitzsimons

Monireh Houshmand, Mahboobeh Houshmand, Si-Hui Tan et al.

The engineering challenges involved in building large scale quantum computers, and the associated infrastructure requirements, mean that when such devices become available it is likely that this will be in limited numbers and in limited geographic locations. It is likely that many users will need to rely on remote access to delegate their computation to the available hardware. In such a scenario, the privacy and reliability of the delegated computations are important concerns. On the other hand, the distributed nature of modern computations has led to a widespread class of applications in which a group of parties attempt to perform a joint task over their inputs, e.g., in cloud computing. In this paper, we study the multi-client delegated quantum computation problem where we consider the global computation be made up of local computations that are individually decided by the clients. Each client part is kept secret from the server and the other clients. We construct a composable secure multi-client delegated quantum computation scheme from any composable secure single-client delegated quantum computation protocol and quantum authentication codes.

Zhikuan Zhao, Jack K. Fitzsimons, Patrick Rebentrost et al.

Machine learning has recently emerged as a fruitful area for finding potential quantum computational advantage. Many of the quantum enhanced machine learning algorithms critically hinge upon the ability to efficiently produce states proportional to high-dimensional data points stored in a quantum accessible memory. Even given query access to exponentially many entries stored in a database, the construction of which is considered a one-off overhead, it has been argued that the cost of preparing such amplitude-encoded states may offset any exponential quantum advantage. Here we prove using smoothed analysis, that if the data-analysis algorithm is robust against small entry-wise input perturbation, state preparation can always be achieved with constant queries. This criterion is typically satisfied in realistic machine learning applications, where input data is subjective to moderate noise. Our results are equally applicable to the recent seminal progress in quantum-inspired algorithms, where specially constructed databases suffice for polylogarithmic classical algorithm in low-rank cases. The consequence of our finding is that for the purpose of practical machine learning, polylogarithmic processing time is possible under a general and flexible input model with quantum algorithms or quantum-inspired classical algorithms in the low-rank cases.

Zhikuan Zhao, Jack K. Fitzsimons, Michael A. Osborne et al.

Gaussian processes (GPs) are important models in supervised machine learning. Training in Gaussian processes refers to selecting the covariance functions and the associated parameters in order to improve the outcome of predictions, the core of which amounts to evaluating the logarithm of the marginal likelihood (LML) of a given model. LML gives a concrete measure of the quality of prediction that a GP model is expected to achieve. The classical computation of LML typically carries a polynomial time overhead with respect to the input size. We propose a quantum algorithm that computes the logarithm of the determinant of a Hermitian matrix, which runs in logarithmic time for sparse matrices. This is applied in conjunction with a variant of the quantum linear system algorithm that allows for logarithmic time computation of the form $\mathbf{y}^TA^{-1}\mathbf{y}$, where $\mathbf{y}$ is a dense vector and $A$ is the covariance matrix. We hence show that quantum computing can be used to estimate the LML of a GP with exponentially improved efficiency under certain conditions.

Tommaso F. Demarie, Yingkai Ouyang, Joseph F. Fitzsimons

We consider the task of verifying the correctness of quantum computation for a restricted class of circuits which contain at most two basis changes. This contains circuits giving rise to the second level of the Fourier Hierarchy, the lowest level for which there is an established quantum advantage. We show that, when the circuit has an outcome with probability at least the inverse of some polynomial in the circuit size, the outcome can be checked in polynomial time with bounded error by a completely classical verifier. This verification procedure is based on random sampling of computational paths and is only possible given knowledge of the likely outcome.

Joseph F. Fitzsimons

Quantum technologies hold the promise of not only faster algorithmic processing of data, via quantum computation, but also of more secure communications, in the form of quantum cryptography. In recent years, a number of protocols have emerged which seek to marry these concepts for the purpose of securing computation rather than communication. These protocols address the task of securely delegating quantum computation to an untrusted device while maintaining the privacy, and in some instances the integrity, of the computation. We present a review of the progress to date in this emerging area.

J. K. Fitzsimons, M. A. Osborne, S. J. Roberts et al.

We examine the problem of estimating the trace of a matrix $A$ when given access to an oracle which computes $x^\dagger A x$ for an input vector $x$. We make use of the basis vectors from a set of mutually unbiased bases, widely studied in the field of quantum information processing, in the selection of probing vectors $x$. This approach offers a new state of the art single shot sampling variance while requiring only $O(\log(n))$ random bits to generate each vector. This significantly improves on traditional methods such as Hutchinson's and Gaussian estimators in terms of the number of random bits required and worst case sample variance.

Joseph F. Fitzsimons, Michal Hajdušek

With recent progress on experimental quantum information processing, an important question has arisen as to whether it is possible to verify arbitrary computation performed on a quantum processor. A number of protocols have been proposed to achieve this goal, however all are interactive in nature, requiring that the computation be performed in an interactive manner with back and forth communication between the verifier and one or more provers. Here we propose two methods for verifying quantum computation in a non-interactive manner based on recent progress in the understanding of the local Hamiltonian problem. Provided that the provers compute certain witnesses for the computation, this allows the result of a quantum computation to be verified after the fact, a property not seen in current verification protocols.

Zhikuan Zhao, Jack K. Fitzsimons, Joseph F. Fitzsimons

Gaussian processes (GP) are a widely used model for regression problems in supervised machine learning. Implementation of GP regression typically requires $O(n^3)$ logic gates. We show that the quantum linear systems algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] can be applied to Gaussian process regression (GPR), leading to an exponential reduction in computation time in some instances. We show that even in some cases not ideally suited to the quantum linear systems algorithm, a polynomial increase in efficiency still occurs.

Michal Hajdušek, Carlos A. Pérez-Delgado, Joseph F. Fitzsimons

As progress on experimental quantum processors continues to advance, the problem of verifying the correct operation of such devices is becoming a pressing concern. The recent discovery of protocols for verifying computation performed by entangled but non-communicating quantum processors holds the promise of certifying the correctness of arbitrary quantum computations in a fully device-independent manner. Unfortunately, all known schemes have prohibitive overhead, with resources scaling as extremely high degree polynomials in the number of gates constituting the computation. Here we present a novel approach based on a combination of verified blind quantum computation and Bell state self-testing. This approach has dramatically reduced overhead, with resources scaling as only $O(m^4\ln m)$ in the number of gates.

Li Yu, Carlos A. Perez-Delgado, Joseph F. Fitzsimons

Homomorphic encryption is a form of encryption which allows computation to be carried out on the encrypted data without the need for decryption. The success of quantum approaches to related tasks in a delegated computation setting has raised the question of whether quantum mechanics may be used to achieve information theoretically secure fully homomorphic encryption. Here we show, via an information localisation argument, that deterministic fully homomorphic encryption necessarily incurs exponential overhead if perfect security is required.

Vedran Dunjko, Joseph F. Fitzsimons, Christopher Portmann et al.

Delegating difficult computations to remote large computation facilities, with appropriate security guarantees, is a possible solution for the ever-growing needs of personal computing power. For delegated computation protocols to be usable in a larger context---or simply to securely run two protocols in parallel---the security definitions need to be composable. Here, we define composable security for delegated quantum computation. We distinguish between protocols which provide only blindness---the computation is hidden from the server---and those that are also verifiable---the client can check that it has received the correct result. We show that the composable security definition capturing both these notions can be reduced to a combination of several distinct "trace-distance-type" criteria---which are, individually, non-composable security definitions. Additionally, we study the security of some known delegated quantum computation protocols, including Broadbent, Fitzsimons and Kashefi's Universal Blind Quantum Computation protocol. Even though these protocols were originally proposed with insufficient security criteria, they turn out to still be secure given the stronger composable definitions.