@article {3394, title = {Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model}, year = {2023}, month = {12/17/2023}, abstract = {

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium, Dilithium-QROM, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key sizes and signature sizes are about 2.5 to 2.8 times larger than those of Dilithium-QROM for the same security levels.

}, url = {https://arxiv.org/abs/2312.16619}, author = {Kelsey A. Jackson and Carl Miller and Daochen Wang} } @article {3271, title = {Parallel self-testing of EPR pairs under computational assumptions}, year = {2023}, month = {3/29/2023}, abstract = {

Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.

}, url = {https://arxiv.org/abs/2201.13430}, author = {Honghao Fu and Daochen Wang and Qi Zhao} } @article {3272, title = {Parallel self-testing of EPR pairs under computational assumptions}, year = {2023}, month = {3/29/2023}, abstract = {

Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.

}, url = {https://arxiv.org/abs/2201.13430}, author = {Honghao Fu and Daochen Wang and Qi Zhao} } @article {3429, title = {On the Rational Degree of Boolean Functions and Applications}, year = {2023}, month = {10/12/2023}, abstract = {

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least deg(f)\−\−\−\−\−\√. We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2\−O(n\−\−\√).
In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model.

}, url = {arXiv:2310.08004}, author = {Vishnu Iyer and Siddhartha Jain and Matt Kovacs-Deak and Vinayak M. Kumar and Luke Schaeffer and Daochen Wang and Michael Whitmeyer} } @article {3270, title = {A theory of quantum differential equation solvers: limitations and fast-forwarding}, year = {2023}, month = {3/2/2023}, abstract = {

We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic homogeneous linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of {\textquoteleft}{\textquoteleft}non-quantumness\&$\#$39;\&$\#$39;: real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of {\textquoteleft}{\textquoteleft}non-quantumness\&$\#$39;\&$\#$39; are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain quadratic improvements in the evolution time T for inhomogeneous ODEs with a negative semi-definite coefficient matrix, and exponential improvements in both T and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.

}, url = {https://arxiv.org/abs/2211.05246}, author = {Dong An and Jin-Peng Liu and Daochen Wang and Qi Zhao} } @article {3021, title = {Computational self-testing of multi-qubit states and measurements}, year = {2022}, month = {1/31/2022}, abstract = {

Self-testing is a fundamental technique within quantum information theory that allows a classical verifier to force (untrusted) quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under standard computational assumptions. In this work, we generalize their techniques to give the first protocol that self-tests N EPR pairs and measurements in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a cloud quantum computer, on which we cannot enforce spatial separation, using only classical communication.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2201.13430}, url = {https://arxiv.org/abs/2201.13430}, author = {Fu, Honghao and Daochen Wang and Zhao, Qi} } @article {2426, title = {Efficient quantum measurement of Pauli operators}, journal = {Quantum}, volume = {5}, year = {2021}, month = {01/19/2021}, chapter = {385}, abstract = {

Estimating the expectation value of an observable is a fundamental task in quantum computation. Unfortunately, it is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the observable into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version first groups mutually commuting Pauli operators together and then measures all operators within each group simultaneously. The effectiveness of this depends on two factors. First, to enable simultaneous measurement, circuits are required to rotate each group to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any group of k commuting n-qubit Pauli operators using at most kn\−k(k+1)/2 and O(kn/logk) two-qubit gates respectively. Second, metrics that justifiably measure the effectiveness of a grouping are required. In our work, we propose two natural metrics that operate under the assumption that measurements are distributed optimally among groups. Motivated by our new metrics, we introduce SORTED INSERTION, a grouping strategy that is explicitly aware of the weighting of each Pauli operator in the observable. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the observables in question are molecular Hamiltonians. As measured by our metrics, SORTED INSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of groups.

}, doi = {https://doi.org/10.22331/q-2021-01-20-385}, url = {https://arxiv.org/abs/1908.06942}, author = {Ophelia Crawford and Barnaby van Straaten and Daochen Wang and Thomas Parks and Earl Campbell and Stephen Brierley} } @article {3022, title = {Quantum Algorithms for Reinforcement Learning with a Generative Model}, journal = {Proceedings of the 38th International Conference on Machine Learning, PMLR}, volume = {139}, year = {2021}, month = {12/15/2021}, chapter = {10916-10926}, abstract = {

Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a γ-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (π\∗), the optimal value function (v\∗), and the optimal Q-function (q\∗), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy (ϵ) and two main parameters of the MDP: the effective time horizon (11\−γ) and the size of the action space (A). Moreover, we show that our quantum algorithm for computing q\∗ is optimal by proving a matching quantum lower bound.

}, keywords = {FOS: Computer and information sciences, FOS: Physical sciences, Machine Learning (cs.LG), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2112.08451}, url = {https://arxiv.org/abs/2112.08451}, author = {Daochen Wang and Sundaram, Aarthi and Kothari, Robin and Kapoor, Ashish and Roetteler, Martin} } @article {2633, title = {Quantum exploration algorithms for multi-armed bandits}, journal = {Proceedings of the 35th Conference on Artificial Intelligence (AAAI 2021)}, volume = {35}, year = {2021}, month = {2021}, pages = {10102-10110}, abstract = {

\ Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we show that we can find the best arm with fixed confidence using O~(\∑ni=2Δ\−2i\−\−\−\−\−\−\−\−\√) quantum queries, where Δi represents the difference between the mean reward of the best arm and the ith-best arm. This algorithm, based on variable-time amplitude amplification and estimation, gives a quadratic speedup compared to the best possible classical result. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/17212}, author = {Daochen Wang and Xuchen You and Tongyang Li and Andrew M. Childs} } @article {2526, title = {Can graph properties have exponential quantum speedup?}, year = {2020}, month = {1/28/2020}, abstract = {

Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity R of any graph property P has R(P)=O(Q(P)6), where Q is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l) for any l-uniform hypergraph property P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

}, url = {https://arxiv.org/abs/2001.10520}, author = {Andrew M. Childs and Daochen Wang} } @conference {2599, title = {Symmetries, graph properties, and quantum speedups}, booktitle = {Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649{\textendash}660 (2020)}, year = {2020}, month = {6/23/2020}, abstract = {

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup?
In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups.
In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

}, doi = {https://doi.org/10.1109/FOCS46700.2020.00066}, url = {https://arxiv.org/abs/2006.12760}, author = {Shalev Ben-David and Andrew M. Childs and Andras Gilyen and William Kretschmer and Supartha Podder and Daochen Wang} } @article {2562, title = {Accelerated Variational Quantum Eigensolver}, journal = {Phys. Rev. Lett. }, volume = {122}, year = {2019}, month = {3/25/2019}, abstract = {

The problem of finding the ground state energy of a Hamiltonian using a quantum computer is currently solved using either the quantum phase estimation (QPE) or variational quantum eigensolver (VQE) algorithms. For precision ε, QPE requires O(1) repetitions of circuits with depth O(1/ε), whereas each expectation estimation subroutine within VQE requires O(1/ε2) samples from circuits with depth O(1). We propose a generalised VQE algorithm that interpolates between these two regimes via a free parameter α\∈[0,1] which can exploit quantum coherence over a circuit depth of O(1/εα) to reduce the number of samples to O(1/ε2(1\−α)). Along the way, we give a new routine for expectation estimation under limited quantum resources that is of independent interest.

}, doi = {https://doi.org/10.1103/PhysRevLett.122.140504}, url = {https://arxiv.org/abs/1802.00171}, author = {Daochen Wang and Oscar Higgott and Stephen Brierley} } @article {2391, title = {Simulating quantum circuits by classical circuits}, year = {2019}, month = {04/10/2019}, abstract = {

In a recent breakthrough, Bravyi, Gosset and K{\"o}nig (BGK) [Science, 2018] proved that \"simulating\" constant depth quantum circuits takes classical circuits Ω(logn) depth. In our paper, we first formalise their notion of simulation, which we call \"possibilistic simulation\". Then, from well-known results, we deduce that their circuits can be simulated in depth O(log2n). Separately, we construct explicit classical circuits that can simulate any depth-d quantum circuit with Clifford and t T-gates in depth O(d+t). Our classical circuits use {NOT, AND, OR} gates of fan-in \≤2.

}, url = {https://arxiv.org/abs/1904.05282}, author = {Daochen Wang} } @article {2416, title = {Variational Quantum Computation of Excited States}, journal = {Quantum }, volume = {3}, year = {2019}, month = {06/28/2019}, abstract = {

The calculation of excited state energies of electronic structure Hamiltonians has many important applications, such as the calculation of optical spectra and reaction rates. While low-depth quantum algorithms, such as the variational quantum eigenvalue solver (VQE), have been used to determine ground state energies, methods for calculating excited states currently involve the implementation of high-depth controlled-unitaries or a large number of additional samples. Here we show how overlap estimation can be used to deflate eigenstates once they are found, enabling the calculation of excited state energies and their degeneracies. We propose an implementation that requires the same number of qubits as VQE and at most twice the circuit depth. Our method is robust to control errors, is compatible with error-mitigation strategies and can be implemented on near-term quantum compute

}, doi = {https://doi.org/10.22331/q-2019-07-01-156}, url = {https://arxiv.org/abs/1805.08138}, author = {Oscar Higgott and Daochen Wang and Stephen Brierley} } @article {2561, title = {Driving Rabi oscillations at the giant dipole resonance in xenon}, journal = {Phys. Rev. A }, volume = {92}, year = {2015}, month = {11/23/2015}, abstract = {

Free-electron lasers (FELs) produce short and very intense light pulses in the XUV and x-ray regimes. We investigate the possibility to drive Rabi oscillations in xenon with an intense FEL pulse by using the unusually large dipole strength of the giant-dipole resonance (GDR). The GDR decays within less than 30 as due to its position, which is above the 4d ionization threshold. We find that intensities around 1018 W/cm2 are required to induce Rabi oscillations with a period comparable to the lifetime. The pulse duration should not exceed 100 as because xenon will be fully ionized within a few lifetimes. Rabi oscillations reveal themselves also in the photoelectron spectrum in form of Autler-Townes splittings extending over several tens of electronvolt.

}, doi = {https://doi.org/10.1103/PhysRevA.92.053424}, url = {https://arxiv.org/abs/1511.00058}, author = {Stefan Pabst and Daochen Wang and Robin Santra} }