@article {3517, title = {Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding}, year = {2024}, month = {1/16/2024}, abstract = {

Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices.
In this paper, we propose a technique named Hamiltonian embedding. This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schr{\"o}dinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.

}, url = {https://arxiv.org/abs/2401.08550}, author = {Jiaqi Leng and Joseph Li and Yuxiang Peng and Xiaodi Wu} } @article {3496, title = {The Quantum Abstract Machine}, year = {2024}, month = {2/21/2024}, abstract = {

This paper develops a model of quantum behavior that is intended to support the abstract yet accurate design and functional verification of quantum communication protocols. The work is motivated by the need for conceptual tools for the development of quantum-communication systems that are usable by non-specialists in quantum physics while also correctly capturing at a useful abstraction the underlying quantum phenomena. Our approach involves defining a quantum abstract machine (QAM) whose operations correspond to well-known quantum circuits; these operations, however, are given direct abstract semantics in a style similar to that of Berry\&$\#$39;s and Boudol\&$\#$39;s Chemical Abstract Machine. This paper defines the QAM\&$\#$39;s semantics and shows via examples how it may be used to model and reason about existing quantum communication protocols.

}, url = {https://arxiv.org/abs/2402.13469}, author = {Liyi Li and Le Chang and Rance Cleaveland and Mingwei Zhu and Xiaodi Wu} } @article {3246, title = {Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels}, year = {2023}, month = {3/26/2023}, abstract = {

A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training and implies that the range of measurements is crucial to the fast QNN convergence.

}, url = {https://arxiv.org/abs/2303.14844}, author = {Xuchen You and Shouvanik Chakrabarti and Boyang Chen and Xiaodi Wu} } @article {3395, title = {Microwave signal processing using an analog quantum reservoir computer}, year = {2023}, month = {12/26/2023}, abstract = {

Quantum reservoir computing (QRC) has been proposed as a paradigm for performing machine learning with quantum processors where the training is efficient in the number of required runs of the quantum processor and takes place in the classical domain, avoiding the issue of barren plateaus in parameterized-circuit quantum neural networks. It is natural to consider using a quantum processor based on superconducting circuits to classify microwave signals that are analog -- continuous in time. However, while theoretical proposals of analog QRC exist, to date QRC has been implemented using circuit-model quantum systems -- imposing a discretization of the incoming signal in time, with each time point input by executing a gate operation. In this paper we show how a quantum superconducting circuit comprising an oscillator coupled to a qubit can be used as an analog quantum reservoir for a variety of classification tasks, achieving high accuracy on all of them. Our quantum system was operated without artificially discretizing the input data, directly taking in microwave signals. Our work does not attempt to address the question of whether QRCs could provide a quantum computational advantage in classifying pre-recorded classical signals. However, beyond illustrating that sophisticated tasks can be performed with a modest-size quantum system and inexpensive training, our work opens up the possibility of achieving a different kind of advantage than a purely computational advantage: superconducting circuits can act as extremely sensitive detectors of microwave photons; our work demonstrates processing of ultra-low-power microwave signals in our superconducting circuit, and by combining sensitive detection with QRC processing within the same system, one could achieve a quantum sensing-computational advantage, i.e., an advantage in the overall analysis of microwave signals comprising just a few photons.

}, url = {https://arxiv.org/abs/2312.16166}, author = {Alen Senanian and Sridhar Prabhu and Vladimir Kremenetski and Saswata Roy and Yingkang Cao and Jeremy Kline and Tatsuhiro Onodera and Logan G. Wright and Xiaodi Wu and Valla Fatemi and Peter L. McMahon} } @article {3314, title = {Qafny: Quantum Program Verification Through Type-guided Classical Separation Logic}, year = {2023}, month = {7/12/2023}, abstract = {

Formal verification has been proven instrumental to ensure that quantum programs implement their specifications but often requires a significant investment of time and labor. To address this challenge, we present Qafny, an automated proof system designed for verifying quantum programs. At its core, Qafny uses a type-guided quantum proof system that translates quantum operations to classical array operations. By modeling these operations as proof rules within a classical separation logic framework, Qafny provides automated support for the reasoning process that would otherwise be tedious and time-consuming. We prove the soundness and completeness of our proof system and implement a prototype compiler that transforms Qafny programs both into the Dafny programming language and into executable quantum circuits. Using Qafny, we demonstrate how to efficiently verify prominent quantum algorithms, including quantum-walk algorithms, Grover\&$\#$39;s search algorithm, and Shor\&$\#$39;s factoring algorithm, with significantly reduced human efforts.

}, url = {https://arxiv.org/abs/2211.06411}, author = {Liyi Li and Mingwei Zhu and Rance Cleaveland and Yi Lee and Le Chang and Xiaodi Wu} } @article {2448, title = {Quantum algorithm for estimating volumes of convex bodies}, journal = {ACM Transactions on Quantum Computing}, volume = {4}, year = {2023}, month = {4/2023}, chapter = {20}, abstract = {

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error ε using O~(n3.5+n2.5/ε) queries to a membership oracle and O~(n5.5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses O~(n4+n3/ε2) queries and O~(n6+n5/ε2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of \"Chebyshev cooling\", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.

}, url = {https://arxiv.org/abs/1908.03903}, author = {Shouvanik Chakrabarti and Andrew M. Childs and Shih-Han Hung and Tongyang Li and Chunhao Wang and Xiaodi Wu} } @article {3411, title = {A quantum central path algorithm for linear optimization}, year = {2023}, month = {11/7/2023}, abstract = {

We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. Combining our approach with iterative refinement techniques, we obtain an exact solution to a linear optimization problem involving m constraints and n variables using at most O((m+n)nnz(A)κ(M)L\⋅polylog(m,n,κ(M))) elementary gates and O(nnz(A)L) classical arithmetic operations, where nnz(A) is the total number of non-zero elements found in the constraint matrix, L denotes binary input length of the problem data, and κ(M) is a condition number that depends only on the problem data.

}, url = {https://arxiv.org/abs/2311.03977}, author = {Brandon Augustino and Jiaqi Leng and Giacomo Nannicini and Tam{\'a}s Terlaky and Xiaodi Wu} } @article {3250, title = {Quantum Hamiltonian Descent}, year = {2023}, month = {3/2/2023}, abstract = {

Gradient descent is a fundamental algorithm in both theory and practice for continuous optimization. Identifying its quantum counterpart would be appealing to both theoretical and practical quantum applications. A conventional approach to quantum speedups in optimization relies on the quantum acceleration of intermediate steps of classical algorithms, while keeping the overall algorithmic trajectory and solution quality unchanged. We propose Quantum Hamiltonian Descent (QHD), which is derived from the path integral of dynamical systems referring to the continuous-time limit of classical gradient descent algorithms, as a truly quantum counterpart of classical gradient methods where the contribution from classically-prohibited trajectories can significantly boost QHD\&$\#$39;s performance for non-convex optimization. Moreover, QHD is described as a Hamiltonian evolution efficiently simulatable on both digital and analog quantum computers. By embedding the dynamics of QHD into the evolution of the so-called Quantum Ising Machine (including D-Wave and others), we empirically observe that the D-Wave-implemented QHD outperforms a selection of state-of-the-art gradient-based classical solvers and the standard quantum adiabatic algorithm, based on the time-to-solution metric, on non-convex constrained quadratic programming instances up to 75 dimensions. Finally, we propose a \"three-phase picture\" to explain the behavior of QHD, especially its difference from the quantum adiabatic algorithm.

}, url = {https://arxiv.org/abs/2303.01471}, author = {Jiaqi Leng and Ethan Hickman and Joseph Li and Xiaodi Wu} } @article {3397, title = {Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions}, year = {2023}, month = {12/14/2023}, abstract = {

Computational models are an essential tool for the design, characterization, and discovery of novel materials. Hard computational tasks in materials science stretch the limits of existing high-performance supercomputing centers, consuming much of their simulation, analysis, and data resources. Quantum computing, on the other hand, is an emerging technology with the potential to accelerate many of the computational tasks needed for materials science. In order to do that, the quantum technology must interact with conventional high-performance computing in several ways: approximate results validation, identification of hard problems, and synergies in quantum-centric supercomputing. In this paper, we provide a perspective on how quantum-centric supercomputing can help address critical computational problems in materials science, the challenges to face in order to solve representative use cases, and new suggested directions.

}, url = {https://arxiv.org/abs/2312.09733}, author = {Yuri Alexeev and Maximilian Amsler and Paul Baity and Marco Antonio Barroca and Sanzio Bassini and Torey Battelle and Daan Camps and David Casanova and Young jai Choi and Frederic T. Chong and Charles Chung and Chris Codella and Antonio D. Corcoles and James Cruise and Alberto Di Meglio and Jonathan Dubois and Ivan Duran and Thomas Eckl and Sophia Economou and Stephan Eidenbenz and Bruce Elmegreen and Clyde Fare and Ismael Faro and Cristina Sanz Fern{\'a}ndez and Rodrigo Neumann Barros Ferreira and Keisuke Fuji and Bryce Fuller and Laura Gagliardi and Giulia Galli and Jennifer R. Glick and Isacco Gobbi and Pranav Gokhale and Salvador de la Puente Gonzalez and Johannes Greiner and Bill Gropp and Michele Grossi and Emmanuel Gull and Burns Healy and Benchen Huang and Travis S. Humble and Nobuyasu Ito and Artur F. Izmaylov and Ali Javadi-Abhari and Douglas Jennewein and Shantenu Jha and Liang Jiang and Barbara Jones and Wibe Albert de Jong and Petar Jurcevic and William Kirby and Stefan Kister and Masahiro Kitagawa and Joel Klassen and Katherine Klymko and Kwangwon Koh and Masaaki Kondo and Doga Murat Kurkcuoglu and Krzysztof Kurowski and Teodoro Laino and Ryan Landfield and Matt Leininger and Vicente Leyton-Ortega and Ang Li and Meifeng Lin and Junyu Liu and Nicolas Lorente and Andre Luckow and Simon Martiel and Francisco Martin-Fernandez and Margaret Martonosi and Claire Marvinney and Arcesio Castaneda Medina and Dirk Merten and Antonio Mezzacapo and Kristel Michielsen and Abhishek Mitra and Tushar Mittal and Kyungsun Moon and Joel Moore and Mario Motta and Young-Hye Na and Yunseong Nam and Prineha Narang and Yu-ya Ohnishi and Daniele Ottaviani and Matthew Otten and Scott Pakin and Vincent R. Pascuzzi and Ed Penault and Tomasz Piontek and Jed Pitera and Patrick Rall and Gokul Subramanian Ravi and Niall Robertson and Matteo Rossi and Piotr Rydlichowski and Hoon Ryu and Georgy Samsonidze and Mitsuhisa Sato and Nishant Saurabh and Vidushi Sharma and Kunal Sharma and Soyoung Shin and George Slessman and Mathias Steiner and Iskandar Sitdikov and In-Saeng Suh and Eric Switzer and Wei Tang and Joel Thompson and Synge Todo and Minh Tran and Dimitar Trenev and Christian Trott and Huan-Hsin Tseng and Esin Tureci and David Garc{\'\i}a Valinas and Sofia Vallecorsa and Christopher Wever and Konrad Wojciechowski and Xiaodi Wu and Shinjae Yoo and Nobuyuki Yoshioka and Victor Wen-zhe Yu and Seiji Yunoki and Sergiy Zhuk and Dmitry Zubarev} } @article {3412, title = {A quantum-classical performance separation in nonconvex optimization}, year = {2023}, month = {11/1/2023}, abstract = {

In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2d local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any d-dimensional instance from this family using O\˜(d3) quantum queries to the function value and O\˜(d4) additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.

}, url = {https://arxiv.org/abs/2311.00811}, author = {Jiaqi Leng and Yufan Zheng and Xiaodi Wu} } @article {3249, title = {SimuQ: A Domain-Specific Language For Quantum Simulation With Analog Compilation}, year = {2023}, month = {3/5/2023}, abstract = {

Hamiltonian simulation is one of the most promising applications of quantum computing. Recent experimental results suggest that continuous-time analog quantum simulation would be advantageous over gate-based digital quantum simulation in the Noisy Intermediate-Size Quantum (NISQ) machine era. However, programming such analog quantum simulators is much more challenging due to the lack of a unified interface between hardware and software, and the only few known examples are all hardware-specific. In this paper, we design and implement SimuQ, the first domain-specific language for Hamiltonian simulation that supports pulse-level compilation to heterogeneous analog quantum simulators. Specifically, in SimuQ, front-end users will specify the target Hamiltonian evolution with a Hamiltonian modeling language, and the programmability of analog simulators is specified through a new abstraction called the abstract analog instruction set by hardware providers. Through a solver-based compilation, SimuQ will generate the pulse-level instruction schedule on the target analog simulator for the desired Hamiltonian evolution, which has been demonstrated on pulse-controlled superconducting (Qiskit Pulse) and neutral-atom (QuEra Bloqade) quantum systems, as well as on normal circuit-based digital quantum machines. Moreover, we also demonstrate the advantage of analog compilation over digital compilation on IBM machines, the use of SimuQ for resource estimation for hypothetical machines, and a scalability test of SimuQ\&$\#$39;s compilation.

}, url = {https://arxiv.org/abs/2303.02775}, author = {Yuxiang Peng and Jacob Young and Pengyu Liu and Xiaodi Wu} } @article {3072, title = {A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers}, year = {2022}, month = {5/25/2022}, abstract = {

The Variational Quantum Eigensolver (VQE) is a promising candidate for quantum applications on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. Despite a lot of empirical studies and recent progress in theoretical understanding of VQE\&$\#$39;s optimization landscape, the convergence for optimizing VQE is far less understood. We provide the first rigorous analysis of the convergence of VQEs in the over-parameterization regime. By connecting the training dynamics with the Riemannian Gradient Flow on the unit-sphere, we establish a threshold on the sufficient number of parameters for efficient convergence, which depends polynomially on the system dimension and the spectral ratio, a property of the problem Hamiltonian, and could be resilient to gradient noise to some extent. We further illustrate that this overparameterization threshold could be vastly reduced for specific VQE instances by establishing an ansatz-dependent threshold paralleling our main result. We showcase that our ansatz-dependent threshold could serve as a proxy of the trainability of different VQE ansatzes without performing empirical experiments, which hence leads to a principled way of evaluating ansatz design. Finally, we conclude with a comprehensive empirical study that supports our theoretical findings

}, url = {https://arxiv.org/abs/2205.12481}, author = {Xuchen You and Shouvanik Chakrabarti and Xiaodi Wu} } @article {2858, title = {Algebraic Reasoning of Quantum Programs via Non-Idempotent Kleene Algebra}, year = {2021}, month = {10/13/2021}, abstract = {

We investigate the algebraic reasoning of quantum programs inspired by the success of classical program analysis based on Kleene algebra. One prominent example of such is the famous Kleene Algebra with Tests (KAT), which has furnished both theoretical insights and practical tools. The succinctness of algebraic reasoning would be especially desirable for scalable analysis of quantum programs, given the involvement of exponential-size matrices in most of the existing methods. A few key features of KAT including the idempotent law and the nice properties of classical tests, however, fail to hold in the context of quantum programs due to their unique quantum features, especially in branching. We propose the Non-idempotent Kleena Algebra (NKA) as a natural alternative and identify complete and sound semantic models for NKA as well as their appropriate quantum interpretations. In light of applications of KAT, we are able to demonstrate algebraic proofs in NKA of quantum compiler optimization and the normal form of quantum while-programs. Moreover, we extend NKA with Tests (i.e., NKAT), where tests model quantum predicates following the rules of effect algebra, and illustrate how to encode propositional quantum Hoare logic as NKAT theorems.

}, doi = {https://doi.org/10.1145/3519939.3523713}, url = {https://arxiv.org/abs/2110.07018}, author = {Yuxiang Peng and Mingsheng Ying and Xiaodi Wu} } @article {2881, title = {EasyPQC: Verifying Post-Quantum Cryptography}, journal = {ACM CCS 2021}, year = {2021}, month = {9/20/2021}, abstract = {

EasyCrypt is a formal verification tool used extensively for formalizing concrete security proofs of cryptographic constructions. However, the EasyCrypt formal logics consider only classical attackers, which means that post-quantum security proofs cannot be formalized and machine-checked with this tool. In this paper we prove that a natural extension of the EasyCrypt core logics permits capturing a wide class of post-quantum cryptography proofs, settling a question raised by (Unruh, POPL 2019). Leveraging our positive result, we implement EasyPQC, an extension of EasyCrypt for post-quantum security proofs, and use EasyPQC to verify post-quantum security of three classic constructions: PRF-based MAC, Full Domain Hash and GPV08 identity-based encryption.

}, doi = {https://dx.doi.org/10.1145/3460120.3484567}, author = {Manuel Barbosa and Gilles Barthe and Xiong Fan and Benjamin Gr{\'e}goire and Shih-Han Hung and Jonathan Katz and Pierre-Yves Strub and Xiaodi Wu and Li Zhou} } @conference {2941, title = {Expanding the VOQC Toolkit}, booktitle = {The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021)}, year = {2021}, month = {06/2021}, abstract = {

voqc [Hietala et al. 2021b] (pronounced \“vox\”) is a compiler for quantum circuits, in the style of
tools like Qiskit [Aleksandrowicz et al. 2019], tket [Cambridge Quantum Computing Ltd 2019],
Quilc [Rigetti Computing 2019], and Cirq [Developers 2021]. What makes voqc different from these
tools is that it has been formally verified in the Coq proof assistant [Coq Development Team 2019].
voqc source programs are expressed in sqir, a simple quantum intermediate representation, which
has a precise mathematical semantics. We use Gallina, Coq\’s programming language, to implement
voqc transformations over sqir programs, and use Coq to prove the source program\’s semantics
are preserved. We then extract these Gallina definitions to OCaml, and compile the OCaml code to
a library that can operate on standard-formatted circuits.
voqc, and sqir, were built to be general-purpose. For example, while we originally designed sqir
for use in verified optimizations, we subsequently found sqir could also be suitable for writing, and
proving correct, source programs [Hietala et al. 2021a]. We have continued to develop the voqc
codebase to expand its reach and utility.
In this abstract, we present new extensions to voqc as an illustration of its flexibility. These
include support for calling voqc transformations from Python, added support for new gate sets
and optimizations, and the extension of our notion of correctness to include mapping-preservation,
which allows us to apply optimizations after mapping, reducing the cost introduced by making a
program conform to hardware constraints.

}, url = {http://rand.cs.uchicago.edu/files/planqc_2021c.pdf}, author = {Kesha Hietala and Liyi Li and Akshaj Gaur and Aaron Green and Robert Rand and Xiaodi Wu and Michael Hicks} } @article {2860, title = {Exponentially Many Local Minima in Quantum Neural Networks}, journal = {Proceedings of the 38th International Conference on Machine Learning, PMLR}, volume = {139}, year = {2021}, month = {10/5/2021}, pages = {12144-12155}, abstract = {

Quantum Neural Networks (QNNs), or the so-called variational quantum circuits, are important quantum applications both because of their similar promises as classical neural networks and because of the feasibility of their implementation on near-term intermediate-size noisy quantum machines (NISQ). However, the training task of QNNs is challenging and much less understood. We conduct a quantitative investigation on the landscape of loss functions of QNNs and identify a class of simple yet extremely hard QNN instances for training. Specifically, we show for typical under-parameterized QNNs, there exists a dataset that induces a loss function with the number of spurious local minima depending exponentially on the number of parameters. Moreover, we show the optimality of our construction by providing an almost matching upper bound on such dependence. While local minima in classical neural networks are due to non-linear activations, in quantum neural networks local minima appear as a result of the quantum interference phenomenon. Finally, we empirically confirm that our constructions can indeed be hard instances in practice with typical gradient-based optimizers, which demonstrates the practical value of our findings.\ 

}, url = {https://arxiv.org/pdf/2110.02479.pdf}, author = {Xuchen You and Xiaodi Wu} } @article {2912, title = {Verified Compilation of Quantum Oracles}, year = {2021}, month = {12/13/2021}, abstract = {

Quantum algorithms often apply classical operations, such as arithmetic or predicate checks, over a quantum superposition of classical data; these so-called oracles are often the largest components of a quantum algorithm. To ease the construction of efficient, correct oracle functions, this paper presents VQO, a high-assurance framework implemented with the Coq proof assistant. The core of VQO is OQASM, the oracle quantum assembly language. OQASM operations move qubits among three different bases via the Quantum Fourier Transform and Hadamard operations, thus admitting important optimizations, but without inducing entanglement and the exponential blowup that comes with it. OQASM\&$\#$39;s design enabled us to prove correct VQO\&$\#$39;s compilers -- from a simple imperative language called OQIMP to OQASM, and from OQASM to SQIR, a general-purpose quantum assembly language -- and allowed us to efficiently test properties of OQASM programs using the QuickChick property-based testing framework. We have used VQO to implement oracles used in Shor\&$\#$39;s and Grover\&$\#$39;s algorithms, as well as several common arithmetic operators. VQO\&$\#$39;s oracles have performance comparable to those produced by Quipper, a state-of-the-art but unverified quantum programming platform.

}, url = {https://arxiv.org/abs/2112.06700}, author = {Liyi Li and Finnegan Voichick and Kesha Hietala and Yuxiang Peng and Xiaodi Wu and Michael Hicks} } @article {2491, title = {A Verified Optimizer for Quantum Circuits}, journal = {Proceedings of the ACM on Programming Languages}, volume = {5}, year = {2021}, month = {11/12/2020}, abstract = {

We present VOQC, the first fully verified compiler for quantum circuits, written using the Coq proof assistant. Quantum circuits are expressed as programs in a simple, low-level language called SQIR, which is deeply embedded in Coq. Optimizations and other transformations are expressed as Coq functions, which are proved correct with respect to a semantics of SQIR programs. We evaluate VOQC\&$\#$39;s verified optimizations on a series of benchmarks, and it performs comparably to industrial-strength compilers. VOQC\&$\#$39;s optimizations reduce total gate counts on average by 17.7\% on a benchmark of 29 circuit programs compared to a 10.7\% reduction when using IBM\&$\#$39;s Qiskit compiler.

}, doi = {https://doi.org/10.1145/3434318}, url = {https://arxiv.org/abs/1912.02250}, author = {Kesha Hietala and Robert Rand and Shih-Han Hung and Xiaodi Wu and Michael Hicks} } @article {2723, title = {Constant-round Blind Classical Verification of Quantum Sampling}, year = {2020}, month = {12/8/2020}, abstract = {

In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affirmative solutions to both as follows. (1) Motivated by the sampling nature of many quantum applications (e.g., quantum algorithms for machine learning and quantum supremacy tasks), we initiate the study of CVQC for quantum sampling problems (denoted by SampBQP). More precisely, in a CVQC protocol for a SampBQP problem, the prover and the verifier are given an input x\∈{0,1}n and a quantum circuit C, and the goal of the classical client is to learn a sample from the output z\←C(x) up to a small error, from its interaction with an untrusted prover. We demonstrate its feasibility by constructing a four-message CVQC protocol for SampBQP based on the quantum Learning With Error assumption. (2) The blindness of CVQC protocols refers to a property of the protocol where the prover learns nothing, and hence is blind, about the client\&$\#$39;s input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. We provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving its completeness and soundness errors as well as the number of rounds. Applying our compiler to (a parallel repetition of) Mahadev\&$\#$39;s CVQC protocol for BQP and our CVQC protocol for SampBQP yields the first constant-round blind CVQC protocol for BQP and SampBQP respectively, with negligible completeness and soundness errors.

}, url = {https://arxiv.org/abs/2012.04848}, author = {Kai-Min Chung and Yi Lee and Han-Hsuan Lin and Xiaodi Wu} } @article {2558, title = {On the Principles of Differentiable Quantum Programming Languages}, year = {2020}, month = {4/2/2020}, abstract = {

Variational Quantum Circuits (VQCs), or the so-called quantum neural-networks, are predicted to be one of the most important near-term quantum applications, not only because of their similar promises as classical neural-networks, but also because of their feasibility on near-term noisy intermediate-size quantum (NISQ) machines. The need for gradient information in the training procedure of VQC applications has stimulated the development of auto-differentiation techniques for quantum circuits. We propose the first formalization of this technique, not only in the context of quantum circuits but also for imperative quantum programs (e.g., with controls), inspired by the success of differentiable programming languages in classical machine learning. In particular, we overcome a few unique difficulties caused by exotic quantum features (such as quantum no-cloning) and provide a rigorous formulation of differentiation applied to bounded-loop imperative quantum programs, its code-transformation rules, as well as a sound logic to reason about their correctness. Moreover, we have implemented our code transformation in OCaml and demonstrated the resource-efficiency of our scheme both analytically and empirically. We also conduct a case study of training a VQC instance with controls, which shows the advantage of our scheme over existing auto-differentiation for quantum circuits without controls.

}, doi = {https://doi.org/10.1145/3385412.3386011}, url = {https://arxiv.org/abs/2004.01122}, author = {Shaopeng Zhu and Shih-Han Hung and Shouvanik Chakrabarti and Xiaodi Wu} } @article {2207, title = {Quantum algorithms and lower bounds for convex optimization}, journal = {Quantum}, volume = {4}, year = {2020}, month = {12/18/2019}, abstract = {

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using O~(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω~(n\−\−\√) evaluation queries and Ω(n\−\−\√) membership queries.

}, doi = {https://doi.org/10.22331/q-2020-01-13-221}, url = {https://arxiv.org/abs/1809.01731}, author = {Shouvanik Chakrabarti and Andrew M. Childs and Tongyang Li and Xiaodi Wu} } @article {2377, title = {Simulating large quantum circuits on a small quantum computer}, journal = {Phys. Rev. Lett.}, volume = {125}, year = {2020}, month = {12/8/2020}, abstract = {

Limited quantum memory is one of the most important constraints for near-term quantum devices. Understanding whether a small quantum computer can simulate a larger quantum system, or execute an algorithm requiring more qubits than available, is both of theoretical and practical importance. In this Letter, we introduce cluster parameters K and d of a quantum circuit. The tensor network of such a circuit can be decomposed into clusters of size at most d with at most K qubits of inter-cluster quantum communication. Our main result is a simulation scheme of any (K,d)-clustered quantum circuit on a d-qubit machine in time roughly 2O(K). An important application of our result is the simulation of clustered quantum systems---such as large molecules---that can be partitioned into multiple significantly smaller clusters with weak interactions among them. Another potential application is quantum optimization: we demonstrate numerically that variational quantum eigensolvers can still perform well when restricted to clustered circuits, thus making it feasible to study large quantum systems on small quantum devices.

}, doi = {https://doi.org/10.1103/PhysRevLett.125.150504}, url = {https://arxiv.org/abs/1904.00102}, author = {Tianyi Peng and Aram Harrow and Maris Ozols and Xiaodi Wu} } @article {2722, title = {Sublinear classical and quantum algorithms for general matrix games}, journal = {To appear in the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)}, year = {2020}, month = {12/11/2020}, abstract = {

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix A\∈Rn\×d, sublinear algorithms for the matrix game minx\∈Xmaxy\∈Yy⊤Ax were previously known only for two special cases: (1) Y being the l1-norm unit ball, and (2) X being either the l1- or the l2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q\∈(1,2], we solve the matrix game where X is a lq-norm unit ball within additive error ε in time O~((n+d)/ε2). We also provide a corresponding sublinear quantum algorithm that solves the same task in time O~((n\−\−\√+d\−\−\√)poly(1/ε)) with a quadratic improvement in both n and d. Both our classical and quantum algorithms are optimal in the dimension parameters n and d up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carath{\'e}odory problem and the lq-margin support vector machines as applications.

}, url = {https://arxiv.org/abs/2012.06519}, author = {Tongyang Li and Chunhao Wang and Shouvanik Chakrabarti and Xiaodi Wu} } @article {2310, title = {Limitations of semidefinite programs for separable states and entangled games}, journal = {Commun. Math. Phys.}, volume = {366}, year = {2019}, month = {03/04/2019}, chapter = {423-468}, abstract = {

Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no ω(1)-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the 2\→4 norm of a matrix, and the set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state. In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Watrous and Aaronson et al. These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz.

}, doi = {https://doi.org/10.1007/s00220-019-03382-y}, url = {https://arxiv.org/abs/1612.09306}, author = {Aram W. Harrow and Anand Natarajan and Xiaodi Wu} } @article {2105, title = {Quantum query complexity of entropy estimation}, journal = {IEEE Transactions on Information Theory}, volume = {65}, year = {2019}, month = {10/16/2017}, pages = {2899-2921}, abstract = {

Estimation of Shannon and R\´enyi entropies of unknown discrete distributions is a fundamental problem in statistical property testing and an active research topic in both theoretical computer science and information theory. Tight bounds on the number of samples to estimate these entropies have been established in the classical setting, while little is known about their quantum counterparts. In this paper, we give the first quantum algorithms for estimating α- R\´enyi entropies (Shannon entropy being 1-Renyi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-R\´enyi entropy estimation for all α \≥ 0, including a tight bound for the collision-entropy (2-R\´enyi entropy). We also provide quantum upper bounds for extreme cases such as the Hartley entropy (i.e., the logarithm of the support size of a distribution, corresponding to α = 0) and the min-entropy case (i.e., α = +\∞), as well as the Kullback-Leibler divergence between two distributions. Moreover, we complement our results with quantum lower bounds on α-R\´enyi entropy estimation for all α \≥ 0. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH) [13] on quantum algorithms for distributional property testing, however, with many new technical ingredients. For Shannon entropy and 0-R\´enyi entropy estimation, we improve the performance of the BHH framework, especially its error dependence, using Montanaro\’s approach to estimating the expected output value of a quantum subroutine with bounded variance [41] and giving a fine-tuned error analysis. For general α-R\´enyi entropy estimation, we further develop a procedure that recursively approximates α-R\´enyi entropy for a sequence of αs, which is in spirit similar to a cooling schedule in simulated annealing. For special cases such as integer α \≥ 2 and α = +\∞ (i.e., the min-entropy), we reduce the entropy estimation problem to the α-distinctness and the dlog ne-distinctness problems, respectively. We exploit various techniques to obtain our lower bounds for different ranges of α, including reductions to (variants of) existing lower bounds in quantum query complexity as well as the polynomial method inspired by the celebrated quantum lower bound for the collision problem.

}, doi = {https://doi.org/10.1109/TIT.2018.2883306}, url = {https://arxiv.org/abs/1710.06025}, author = {Tongyang Li and Xiaodi Wu} } @article {2500, title = {Quantum Wasserstein Generative Adversarial Networks}, journal = {Advances in Neural Information Processing Systems (NIPS)}, volume = {32}, year = {2019}, month = {2019/10/31}, abstract = {

The study of quantum generative models is well-motivated, not only because of its importance in quantum machine learning and quantum chemistry but also because of the perspective of its implementation on near-term quantum machines. Inspired by previous studies on the adversarial training of classical and quantum generative models, we propose the first design of quantum Wasserstein Generative Adversarial Networks (WGANs), which has been shown to improve the robustness and the scalability of the adversarial training of quantum generative models even on noisy quantum hardware. Specifically, we propose a definition of the Wasserstein semimetric between quantum data, which inherits a few key theoretical merits of its classical counterpart. We also demonstrate how to turn the quantum Wasserstein semimetric into a concrete design of quantum WGANs that can be efficiently implemented on quantum machines. Our numerical study, via classical simulation of quantum systems, shows the more robust and scalable numerical performance of our quantum WGANs over other quantum GAN proposals. As a surprising application, our quantum WGAN has been used to generate a 3-qubit quantum circuit of ~50 gates that well approximates a 3-qubit 1-d Hamiltonian simulation circuit that requires over 10k gates using standard techniques.

}, doi = {https://papers.nips.cc/paper/8903-quantum-wasserstein-generative-adversarial-networks.pdf}, url = {https://arxiv.org/abs/1911.00111}, author = {Shouvanik Chakrabarti and Yiming Huang and Tongyang Li and Soheil Feizi and Xiaodi Wu} } @article {2376, title = {Sublinear quantum algorithms for training linear and kernel-based classifiers}, journal = {Proceedings of the 36th International Conference on Machine Learning (ICML 2019) PMLR }, volume = {97}, year = {2019}, month = {04/03/2019}, pages = {3815-3824}, abstract = {

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given n d-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in O~(n+d) time. We design sublinear quantum algorithms for the same task running in O~(n\−\−\√+d\−\−\√) time, a quadratic improvement in both n and d. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of n-dimensional matrix zero-sum games with optimal complexity Θ~(n\−\−\√).\ 

}, url = {https://arxiv.org/abs/1904.02276}, author = {Tongyang Li and Shouvanik Chakrabarti and Xiaodi Wu} } @article {2404, title = {Verified Optimization in a Quantum Intermediate Representation}, year = {2019}, month = {04/12/2019}, abstract = {

We present sqire, a low-level language for quantum computing and verification. sqire uses a global register of quantum bits, allowing easy compilation to and from existing {\textquoteleft}quantum assembly\&$\#$39; languages and simplifying the verification process. We demonstrate the power of sqire as an intermediate representation of quantum programs by verifying a number of useful optimizations, and we demonstrate sqire\&$\#$39;s use as a tool for general verification by proving several quantum programs correct.

}, url = {https://arxiv.org/abs/1904.06319}, author = {Kesha Hietala and Robert Rand and Shih-Han Hung and Xiaodi Wu and Michael Hicks} } @article {2306, title = {Quantitative Robustness Analysis of Quantum Programs (Extended Version)}, journal = {Proc. ACM Program. Lang.}, volume = {3}, year = {2018}, month = {2018/12/1}, pages = {Article 31}, abstract = {

Quantum computation is a topic of significant recent interest, with practical advances coming from both research and industry. A major challenge in quantum programming is dealing with errors (quantum noise) during execution. Because quantum resources (e.g., qubits) are scarce, classical error correction techniques applied at the level of the architecture are currently cost-prohibitive. But while this reality means that quantum programs are almost certain to have errors, there as yet exists no principled means to reason about erroneous behavior. This paper attempts to fill this gap by developing a semantics for erroneous quantum while-programs, as well as a logic for reasoning about them. This logic permits proving a property we have identified, called ε-robustness, which characterizes possible \"distance\" between an ideal program and an erroneous one. We have proved the logic sound, and showed its utility on several case studies, notably: (1) analyzing the robustness of noisy versions of the quantum Bernoulli factory (QBF) and quantum walk (QW); (2) demonstrating the (in)effectiveness of different error correction schemes on single-qubit errors; and (3) analyzing the robustness of a fault-tolerant version of QBF.

}, doi = {https://doi.org/10.1145/3290344}, url = {https://arxiv.org/abs/1811.03585}, author = {Shih-Han Hung and Kesha Hietala and Shaopeng Zhu and Mingsheng Ying and Michael Hicks and Xiaodi Wu} } @article {2309, title = {Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning}, journal = {To appear at the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019)}, year = {2018}, abstract = {

We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank r, and sparsity s. The first algorithm assumes an input model where one is given access to entries of the matrices at unit cost. We show that it has run time O~(s2(m\−\−\√ε\−10+n\−\−\√ε\−12)), where ε is the error. This gives an optimal dependence in terms of m,n and quadratic improvement over previous quantum algorithms when m\≈n. The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is O~(m\−\−\√+poly(r))\⋅poly(logm,logn,B,ε\−1), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in n and polynomially in r. We apply the second SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and copies of an unknown state ρ, we show we can find in time m\−\−\√\⋅poly(logm,logn,r,ε\−1) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements, up to error ε. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes\&$\#$39; principle from statistical mechanics. As in previous work, we obtain our algorithm by \"quantizing\" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could be of independent interest.

}, url = {https://arxiv.org/abs/1710.02581}, author = {Fernando G. S. L. Brand{\~a}o and Amir Kalev and Tongyang Li and Cedric Yen-Yu Lin and Krysta M. Svore and Xiaodi Wu} } @article {2056, title = {Computational Notions of Quantum Min-Entropy}, year = {2017}, month = {2017/09/09}, abstract = {

We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least k, then it has pseudoentropy at least k \− l conditioned on an l- qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relativemin-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g., the Leakage Simulation Lemma, which is proven by a Nonuniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g., Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.

}, url = {https://arxiv.org/abs/1704.07309}, author = {Yi-Hsiu Chen and Kai-Min Chung and Ching-Yi Lai and Salil P. Vadhan and Xiaodi Wu} } @article {2106, title = {Exponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning}, year = {2017}, month = {2017/10/06}, abstract = {

We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ǫ by using \√ m log m \· poly(log n,r, ǫ \−1 ) quantum gates. The dependence on n provides an exponential improvement over the work of Brand \˜ao and Svore [6] and the work of van Apeldoorn et al. [23], and demonstrates an exponential quantum speed-up when m and r are small. We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state ρ, we show we can find in time \√ m log m \· poly(log n,r, ǫ \−1 ) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements up to error ǫ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes\’ principle. As in previous work, we obtain our algorithm by \“quantizing\” classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest. Our quantum SDP solver is different from previous ones in the following two aspects: (1) it follows from a zero-sum game approach of Hazan [11] of solving SDPs rather than the primal-dual approach by Arora and Kale [5]; and (2) it does not rely on any sparsity assumption of the input matrices.

}, url = {https://arxiv.org/abs/1710.02581}, author = {Fernando G. S. L. Brand{\~a}o and Amir Kalev and Tongyang Li and Cedric Yen-Yu Lin and Krysta M. Svore and Xiaodi Wu} } @article {1934, title = {Raz-McKenzie simulation with the inner product gadget}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, year = {2017}, month = {2017/01/28}, abstract = {

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions f composed with the Inner Product gadget 1ip(x, y) = P i xiyi mod 2 of logarithmic size. In other words, given a function f : {0, 1} n \→ {0, 1} with deterministic query complexity D(f), we show that the deterministic communication complexity of the composed function f {\textopenbullet} 1 n ip is Θ(D(f) log n), where f {\textopenbullet} 1 n ip(x, y) = f(1ip(x 1 , y 1 ), . . . , 1ip(x n , y n )) where x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ) and each x i and y i are O(log n) bit strings. In [RM97] and [GPW15], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function f.

}, url = {https://eccc.weizmann.ac.il/report/2017/010/}, author = {Xiaodi Wu and Penghui Yao and Henry Yuen} }