Stacey Jeffery

Aleksandrs Belovs, Stacey Jeffery

Given an algorithm that outputs the correct answer with bounded error, say $1/3$, it is sometimes desirable to reduce this error to some arbitrarily small $\varepsilon$ -- e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of $O(\log\frac{1}{\varepsilon})$ from calling the algorithm this many times. Transducers are a recently introduced model of quantum computation, and it is possible to reduce the ``error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors. In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth. Purifiers can be seen as a way of turning a ``Monte Carlo'' quantum algorithm into a ``Las Vegas'' quantum algorithm -- a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.

Stacey Jeffery, Manideep Mamindlapally, Alex Baudoin Nguetsa Tankeu

The quantum circuit model essentially treats every quantum algorithm as a straight-line program. While this view is universal, recent work has shown that it is inconvenient for using different-length quantum subroutines in superposition. Using the quantum walk formalism of quantum algorithms, it is possible to model such branching behaviour, and get better composition in this setting. We apply the above branching composition to Grover's algorithm, which gives a variable-time quantum search algorithm that is worse than previous work. The reason it is worse is because branching composition does not take into account another deviation from straight-line programs: looping. We show that by modifying branching composition to also include looping, we can get a complexity that matches previous work. This highlights the importance of properly modeling the program control flow when designing quantum algorithms.

Yfke Dulek, Alex B. Grilo, Stacey Jeffery et al.

The cryptographic task of secure multi-party (classical) computation has received a lot of attention in the last decades. Even in the extreme case where a computation is performed between $k$ mutually distrustful players, and security is required even for the single honest player if all other players are colluding adversaries, secure protocols are known. For quantum computation, on the other hand, protocols allowing arbitrary dishonest majority have only been proven for $k=2$. In this work, we generalize the approach taken by Dupuis, Nielsen and Salvail (CRYPTO 2012) in the two-party setting to devise a secure, efficient protocol for multi-party quantum computation for any number of players $k$, and prove security against up to $k-1$ colluding adversaries. The quantum round complexity of the protocol for computing a quantum circuit of $\{\mathsf{CNOT, T}\}$ depth $d$ is $O(k \cdot (d + \log n))$, where $n$ is the security parameter. To achieve efficiency, we develop a novel public verification protocol for the Clifford authentication code, and a testing protocol for magic-state inputs, both using classical multi-party computation.

Gorjan Alagic, Stacey Jeffery, Maris Ozols et al.

Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.

Andrea Coladangelo, Alex Grilo, Stacey Jeffery et al.

The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as $O(g\log g)$ for delegating a circuit of size $g$. This is in contrast to previous protocols, which all require a prohibitively large polynomial overhead. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit being delegated. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem which allows a verifier to test that two entangled provers perform measurements specified by an arbitrary $m$-qubit tensor product of single-qubit Clifford observables on their respective halves of $m$ shared EPR pairs, with a robustness that is independent of $m$. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018).