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.

UR - https://arxiv.org/abs/2001.10520 ER - TY - JOUR T1 - Quantum exploration algorithms for multi-armed bandits JF - To appear in Proceedings of the 35th Conference on Artificial Intelligence (AAAI 2021) Y1 - 2020 A1 - Daochen Wang A1 - Xuchen You A1 - Tongyang Li A1 - Andrew M. Childs AB -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).

UR - https://arxiv.org/abs/2007.07049 ER - TY - JOUR T1 - Symmetries, graph properties, and quantum speedups JF - To appear in Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) Y1 - 2020 A1 - Shalev Ben-David A1 - Andrew M. Childs A1 - Andras Gilyen A1 - William Kretschmer A1 - Supartha Podder A1 - Daochen Wang AB -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).

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.

VL - 122 UR - https://arxiv.org/abs/1802.00171 CP - 140504 U5 - https://doi.org/10.1103/PhysRevLett.122.140504 ER - TY - JOUR T1 - Efficient quantum measurement of Pauli operators Y1 - 2019 A1 - Ophelia Crawford A1 - Barnaby van Straaten A1 - Daochen Wang A1 - Thomas Parks A1 - Earl Campbell A1 - Stephen Brierley AB -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.

UR - https://arxiv.org/abs/1908.06942 ER - TY - JOUR T1 - Simulating quantum circuits by classical circuits Y1 - 2019 A1 - Daochen Wang AB -In a recent breakthrough, Bravyi, Gosset and Kö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.

UR - https://arxiv.org/abs/1904.05282 ER - TY - JOUR T1 - Variational Quantum Computation of Excited States JF - Quantum Y1 - 2019 A1 - Oscar Higgott A1 - Daochen Wang A1 - Stephen Brierley AB -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

VL - 3 UR - https://arxiv.org/abs/1805.08138 CP - 156 U5 - https://doi.org/10.22331/q-2019-07-01-156 ER - TY - JOUR T1 - Driving Rabi oscillations at the giant dipole resonance in xenon JF - Phys. Rev. A Y1 - 2015 A1 - Stefan Pabst A1 - Daochen Wang A1 - Robin Santra AB -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.

VL - 92 UR - https://arxiv.org/abs/1511.00058 CP - 053424 U5 - https://doi.org/10.1103/PhysRevA.92.053424 ER -