Click on a title to see the abstract. The authors of papers in theoretical computer science are listed by the alphabetical order of the last name, whereas in other fields (such as physics, machine learning, programming languages) the authors are listed by contribution where the last author is usually the corresponding author.

Algebraic Reasoning of Quantum Programs via Non-Idempotent Kleene Algebra
(by contribution) Yuxiang Peng, Mingsheng Ying, and Xiaodi Wu. Manuscript, 2020

We investigate 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. As a result, we are able to demonstrate algebraic proofs in NKA of quantum compiler optimization and the normal form of quantum while-programs in light of similar applications of KAT. 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.

Exponentially Many Local Minima in Shallow Quantum Neural Networks
(by contribution) Xuchen You and Xiaodi Wu. Manuscript, 2020.

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 the training. Specifically, we construct a class of 1-layer QNNs with the number of bad 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. Our result resembles some feature of the pioneering work of Auer et al. (NIPS 95) for single classical neurons, however, with the quantum interference phenomenon replacing the non-linear activation for creating bad local minima. Finally, we empirically confirm that our constructions are indeed hard instances in practice with typical optimizers, which demonstrates the practical value of our findings.

Sublinear classical and quantum algorithms for general matrix games
(by contribution) Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu. Manuscript, 2020.

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix Ainmathrm{R}^{ntimes d}, sublinear algorithms for the matrix game min_{xinmathcal{X}}max_{yinmathcal{Y}} y^T Ax were previously known only for two special cases: (1) mathcal{Y} being the ell_{1}-norm unit ball, and (2) mathcal{X} being either the ell_{1}- or the ell_{2}-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed qin (1,2], we solve the matrix game where mathcal{X} is a ell_{q}-norm unit ball within additive error epsilon in time tilde{O}((n+d)/{epsilon^{2}}). We also provide a corresponding sublinear quantum algorithm that solves the same task in time tilde{O}((sqrt{n}+sqrt{d})mathrm{poly}(1/epsilon)) 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 demonstrate sublinear classical and quantum algorithms for the approximate Caratheodory problem and the ell_{q}-margin support vector machines as applications.

Constant-round Blind Classical Verification of Quantum Sampling
Kai-Min Chung, Yi Lee, Han-Hsuan Lin, and Xiaodi Wu. Manuscript, 2020.

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 emph{quantum sampling problems} (denoted by SampBQP). Precisely, given an input xin {0,1}^n and a quantum circuit C, the goal of a classical client is to learn a sample of output z leftarrow C(x) over {0,1}^m with the correct distribution up to a small error from 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's input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. Somewhat surprisingly, we provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving completeness and soundness errors.

Applying our compiler to (a parallel repetition of) Mahadev's 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.

A Verified Optimizer for Quantum Circuits
(by contribution) Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. To appear at the 48th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2021). GitHub

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. SQIR uses a semantics of matrices of complex numbers, which is the standard for quantum computation, but treats matrices symbolically in order to reason about programs that use an arbitrary number of quantum bits. SQIR?s careful design and our provided automation make it easy to write and verify a broad range of optimizations in VOQC, and even allow us to verify correctness properties of interesting source SQIR programs.

On the Theory and Practice of Invariant-based Verification of Quantum Programs
(by contribution) Shih-Han Hung, Yuxiang Peng, Xin Wang, Shaopeng Zhu, and Xiaodi Wu. Manuscript, 2019.

We investigate program verification, a fundamental and challenging task in quantum programming, based on quantum Hoare logic and quantum invariants. Ying et al. (POPL’17) have developed a framework based on semidefinite programs (SDPs) for computing quantum invariants for partial correctness, which is however expensive to use due to its exponential scaling in terms of the number of qubits. In this paper, we develop two approaches that can effectively reuse the information generated from quantum invariants so as to avoid repetitive costs in solving exponentially large SDPs. Our first contribution is the formulation of the master Hoare triple that encodes the complete information of quantum programs inspired by the Choi-Jamiol{}kowski isomorphism. We demonstrate how to obtain the master Hoare triple by a single use of SDP, and once it is generated, how to obtain any other Hoare triple from the master one by a simple logic rule, and how master Hoare triples of sub-programs can be reused to simplify the computation of quantum invariants of the main program. Our second contribution is the introduction of approximate quantum invariants and a framework to reuse invariants of any given quantum program to efficiently analyze its nearby (e.g., noisy, erroneous) programs without using SDPs. Finally, we demonstrate the use of our techniques on realistic quantum programs, such as quantum Hamiltonian simulation and Repeat-Until-Success, with a huge numerical advantage over the previous SDP approach.

On the Principles of Differentiable Quantum Programming Languages
(by contribution) Shaopeng Zhu, Shih-Han Hung, Shouvanik Chakrabarti, and Xiaodi Wu. In the Proceedings of the 41st ACM SIGPLAN PLDI 2020. GitHub.

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 interest and development of auto-differentiation techniques on 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 on quantum circuits without controls.

Quantum algorithm for estimating volumes of convex bodies
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Shih-Han Hung, Chunhao Wang, and Xiaodi Wu. Appeared at QIP 2020 as a single-track talk.

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 epsilon using tilde{O}(n^{3}+n^{2.5}/epsilon) queries to a membership oracle and tilde{O}(n^{5}+n^{4.5}/epsilon) additional arithmetic operations. For comparison, the best known classical algorithm, due to Lovasz and Vempala, uses tilde{O}(n^{4}/epsilon^{2}) queries and tilde{O}(n^{6}/epsilon^{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.

Quantum Wasserstein Generative Adversarial Networks
(by contribution, *= equal contribution) Shouvanik Chakrabarti*, Yiming Huang*, Tongyang Li, Soheil Feizi, and Xiaodi Wu. Appeared at the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS 2019).

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.

Verified Optimization in a Quantum Intermediate Representation
(by contribution) Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. Manuscript, 2019. Extended abstract appeared at Quantum Physics and Logic (QPL) 2019.

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 ‘quantum assembly’ 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's use as a tool for general verification by proving several quantum programs correct.

Simulating large quantum circuits on a small quantum computer
(by contribution) Tianyi Peng, Aram Harrow, Maris Ozols, and Xiaodi Wu . Physical Review Letters 125, 150504.

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 2^{O(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.

Sublinear quantum algorithms for training linear and kernel-based classifiers
(by contribution) Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu . Appeared at the 36th International Conference on Machine Learning (ICML 2019).

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 et al. 2012 runs in tilde{O}(n +d). We design sublinear quantum algorithms for the same task running in tilde{O}(sqrt{n} +sqrt{d}), 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 tilde{Theta}(sqrt{n}).

Quantitative Robustness Analysis of Quantum Programs
(by contribution) Shih-Han Hung, Kesha Hietala, Shaopeng Zhu, Mingsheng Ying, Michael Hicks, and Xiaodi Wu. Appeared at the 46th ACM SIGPLAN POPL 2019.

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 epsilon-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-quibit errors; and (3) analyzing the robustness of a fault-tolerant version of QBF.

Quantum algorithms and lower bounds for convex optimization
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Appeared at QIP 2019.

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 tilde{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 tilde{Omega}(sqrt{n}) evaluation queries and Omega(sqrt{n}) membership queries.

Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning
Fernando G. S. L. Brandao, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Appeared at QIP 2019. To appear at ICALP 2019.

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 at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time tilde{O}(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of n, m and a quadratic improvement over previous quantum algorithms (when m approx n). The second algorithms assumes a fully quantum input model in which the input matrices are given as quantum states. We show its run time is tilde{O}(sqrt{m}+mathrm{poly}(r))cdotmathrm{poly}(log m,log n,B,epsilon^{-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 a supply of copies of an unknown state rho, we show we can find in time sqrt{m}cdotmathrm{poly}(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes’ principle from statistical mechanics.

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, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a ‘‘fast” quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. (SODA 2017). We believe both techniques might be of independent interest.

Quantum query complexity of entropy estimation
Tongyang Li and Xiaodi Wu. IEEE Transaction on Information Theory, Vol. 65, Issue 5, pages 2899 - 2921, May 2019. (link)

Estimation of Shannon and R{'e}nyi 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 of 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 alpha-R{'e}nyi 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 alpha-R{'e}nyi entropy estimation for all alpha>0, including a tight bound for the collision-entropy (2-R{'e}nyi entropy) and also an analysis for the min-entropy case (i.e., alpha=+infty). Moreover, we complement our quantum upper bounds with quantum lower bounds on alpha-R{'e}nyi entropy estimation for all alpha>0.

Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH) on quantum algorithms for distributional property testing, however, with many new technical ingredients. For Shannon 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 and giving a fine-tuned error analysis. For general alpha-R{'e}nyi entropy estimation, we further develop a procedure that recursively approximates alpha-R{'e}nyi entropy for a sequence of alphas, which is in spirit similar to the cooling schedules in simulated annealing. For special cases like integer alphageq 2 and alpha=+infty (i.e., the min-entropy case), we reduce the entropy estimation problem to the alpha-distinctness and the lceillog nrceil-distinctness problems respectively. Finally, we exploit reductions as well as the polynomial method to obtain our lower bounds.

Raz-McKenzie simulation with the inner product gadget
Xiaodi Wu, Penghui Yao, and Henry Yuen . Manuscript, 2017

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 g_{textsc{ip}}(x,y) = sum_i x_iy_i mathrm{ mod } 2 of logarithmic size. In other words, given a function f: {0,1}^n to {0,1} with deterministic query complexity mathsf{D}(f), we show that the deterministic communication complexity of the composed function f circ g_{textsc{ip}}^n is Theta( mathsf{D}(f) log n), where

f circ g_{textsc{ip}}^n (x,y) = f( g_{textsc{ip}}(x^1,y^1),ldots,g_{textsc{ip}}(x^n,y^n)),

x = (x^1,ldots,x^n), y = (y^1,ldots,y^n) and each x^i and y^i are O(log n) bit strings. In Raz-McKenzie and Goos-Pitassi-Watson, 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.

Computational Notions of Quantum Min-Entropy
Yi-Hsiu Chen, Kai-Min Chung, Ching-Yi Lai, Salil P. Vadhan, and Xiaodi Wu . Appeared at the 7th International Conference on Quantum Cryptography (QCrypt 2017).

Computational notions of entropy have many applications in cryptography and complexity theory. These notions measure how much (min-)entropy a source X has from the eyes of a computationally bounded party who may hold certain ?leakage information? B that is correlated with X. In this work, we initiate the study of computational entropy in the quantum setting, where X and/or B may become quantum states and the computationally bounded observer is modelled as a small quantum circuit. Specifically, we investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems still hold. For example, we show:

  • There exist quantum states that are pseudorandom (i.e. they cannot be distinguished from the totally mixed state by polynomial-sized quantum circuits) but have actual entropy 0 (i.e. are pure states). In contrast, a classical distribution needs super-logarithmic entropy to be pseudorandom.

  • We extend the classical Leakage Chain Rule for pseudoentropy to the case where the leakage information B is quantum (while X remains classical). Specifically, if X has pseudoentropy at least k against quantum distinguishers (i.e. it is indistinguishable from some distribution of min-entropy at least k by polynomial-sized quantum distinguishers) and B consists of at most a logarithmic number l of qubits, then X conditioned on B has pseudoentropy at least k-l against quantum distinguishers.

  • We show that a general form of the classical Dense Model Theorem (interpreted as showing the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states.

  • As an application, we construct the first quantum leakage-resilient stream-cipher in the quantum bounded storage model, assuming the existence of a quantum-secure PRG.

Along the way, we develop quantum analogues of a number of classical techniques (e.g. the Leakage Simulation Lemma, proven using a Non-uniform Min-Max Theorem or Boosting), and also identify classical techniques (namely, Gap Amplification) that do not hold in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, which raise a number of directions for future work.

General randomness amplification with non-signaling security
Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu . Appeared at QIP 2017

Highly unpredictable events appear to be abundant in life. However, when modeled rigorously, their existence in nature is far from evident. In fact, the world can be deterministic while at the same time the predictions of quantum mechanics are consistent with observations. Assuming that randomness does exist but only in a weak form, could highly random events be possible? This fundamental question was first raised by Colbeck and Renner (Nature Physics, 8:450–453, 2012). In this work, we answer this question positively, without the various restrictions assumed in the previous works. More precisely, our protocol uses quantum devices, a single weak randomness source quantified by a general notion of non-signaling min-entropy, tolerates a constant amount of device imperfection, and the security is against an all-powerful non-signaling adversary. Unlike the previous works proving non-signaling security, our result does not rely on any structural restrictions or independence assumptions. Thus it implies a stronger interpretation of the dichotomy statement articulated by Gallego et al. (Nature Communications, 4:2654, 2013): ‘‘either our world is fully deterministic or there exist in nature events that are fully random.’’

Note: This is a new work after our QIP 2014 paper, where the security proved is against a quantum, as opposed to non-signaling, adversary.

Limitations of semidefinite programs for separable states and entangled games
Aram Harrow, Anand Natarajan, Xiaodi Wu. Appeared at QIP 2017. Communications in Mathematical Physics, Volume 366, Issue 2, pp 423--468, 2019.

We introduce a method for using reductions to construct integrality gaps for semidefinite programs (SDPs). These imply new limitations on the sum-of-squares (SoS) hierarchy in two settings where previously no omega(1)-round integrality gaps were known:

  • The set of separable (i.e. unentangled) quantum states, or equivalently, the 2rightarrow 4 norm of a matrix.

  • The set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state.

Integrality gaps for the 2rightarrow 4 norm had previously been sought due to its connection to Small-Set Expansion (SSE) and Unique Games (UG).

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 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. Indeed a wide range of past work in quantum information can be described as using an SDP on one of the above two problems and our results put broad limits on these lines of argument.

Invariants of Quantum Programs: Characterizations and Generation
(by contribution) Mingsheng Ying, Shenggang Ying, and Xiaodi Wu . Appeared at the 44th ACM SIGPLAN POPL 2017.

Program invariant is a fundamental notion widely used in program verification and analysis. The aim of this paper is twofold: (i) find an appropriate definition of invariants for quantum programs; and (ii) develop an effective technique of invariant generation for verification and analysis of quantum programs. Interestingly, the notion of invariant can be defined for quantum programs in two different ways – additive invariants and multiplicative invariants – corresponding to two interpretations of implication in a continuous valued logic: the Lukasiewicz implication and the Godel implication. It is shown that both of them can be used to establish partial correctness of quantum programs. The problem of generating additive invariants of quantum programs is addressed by reducing it to an SDP (Semidefinite Programming) problem. This approach is applied with an SDP solver to generate invariants of two important quantum algorithms – quantum walk and quantum Metropolis sampling. Our examples show that the generated invariants can be used to verify correctness of these algorithms and are helpful in optimizing quantum Metropolis sampling. To our knowledge, this paper is the first attempt to define the notion of invariant and to develop a method of invariant generation for quantum programs.

Tight SoS-degree bounds for approximate Nash equilibria

Nash equilibria always exist, but are widely conjectured to require time to find that is exponential in the number of strategies, even for two-player games. By contrast, a simple quasi-polynomial time algorithm, due to Lipton, Markakis and Mehta (LMM), can find approximate Nash equilibria, in which no player can improve their utility by more than epsilon by changing their strategy. The LMM algorithm can also be used to find an approximate Nash equilibrium with near-maximal total welfare. Matching hardness results for this optimization problem were found assuming the hardness of the planted-clique problem (by Hazan and Krauthgamer) and assuming the Exponential Time Hypothesis (by Braverman, Ko and Weinstein).

In this paper we consider the application of the sum-squares (SoS) algorithm from convex optimization to the problem of optimizing over Nash equilibria. We show the first unconditional lower bounds on the number of levels of SoS needed to achieve a constant factor approximation to this problem. While it may seem that Nash equilibria do not naturally lend themselves to convex optimization, we also describe a simple LP (linear programming) hierarchy that can find an approximate Nash equilibrium in time comparable to that of the LMM algorithm, although neither algorithm is obviously a generalization of the other. This LP can be viewed as arising from the SoS algorithm at log n levels — matching our lower bounds. The lower bounds involve a modification of the Braverman-Ko-Weinstein embedding of CSPs into strategic games and techniques from sum-of-squares proof systems. The upper bound (i.e. analysis of the LP) uses information-theory techniques that have been recently applied to other linear- and semidefinite-programming hierarchies.

Sample-optimal tomography of quantum states
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, Nengkun Yu. Appeared at QIP 2016 and STOC 2016.

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error epsilon in trace distance required O(dr^2/epsilon^2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O( (dr/ delta ) ln (d/delta) ) copies of rho to error delta in infidelity, and a matching lower bound up to logarithmic factors. This implies O( (dr / epsilon^2) ln (d/epsilon) ) copies suffice to achieve error epsilon in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.

An improved semidefinite programming hierarchy for testing entanglement
Aram Harrow, Anand Natarajan, Xiaodi Wu. Communications in Mathematical Physics, June 2017, Volume 352, Issue 3, pp 881--904.

We present a stronger version of the Doherty-Parrilo-Spedalieri (DPS) hierarchy of approximations for the set of separable states. Unlike DPS, our hierarchy converges exactly at a finite number of rounds for any fixed input dimension. This yields an algorithm for separability testing which is singly exponential in dimension and polylogarithmic in accuracy. Our analysis makes use of tools from algebraic geometry, but our algorithm is elementary and differs from DPS only by one simple additional collection of constraints.

On the Limits of Communication with Non-local Resources
Xiaodi Wu and Henry Yuen. Manuscript, 2015.

We obtain optimal bounds for the problem of conveying classical messages by communication between a sender and receiver who can utilize non-local correlations obeying the Non-Signaling Principle. These include correlations arising from quantum entanglement, but also include ‘‘super-quantum’’ correlations (e.g. those that maximally violate the CHSH inequality). Our result simultaneously simplifies and generalizes the result of Nayak and Salzman (JACM vol.53, issue 1, pp. 184–206).

Parallel repetition for entangled k-player games via fast quantum search

We present two parallel repetition theorems for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our first theorem shows that for a k-player free game G with entangled value mathrm{val}^*(G) = 1 - epsilon, the n-fold repetition of G has entangled value mathrm{val}^*(G^{otimes n}) at most (1 - epsilon^{3/2})^{Omega(n/sk^4)}, where s is the answer length of any player. In contrast, the best known parallel repetition theorem for the emph{classical} value of two-player free games is mathrm{val}(G^{otimes n}) leq (1 - epsilon^2)^{Omega(n/s)}, due to Barak, et al. (RANDOM 2009). This suggests the possibility of a separation between the behavior of entangled and classical free games under parallel repetition. Our second theorem handles the broader class of free games G where the players can output (possibly entangled) quantum states. For such games, the repeated entangled value is upper bounded by (1 - epsilon^2)^{Omega(n/sk^2)}. We also show that the dependence of the exponent on k is necessary: we exhibit a k-player free game G and n geq 1 such that mathrm{val}^*(G^{otimes n}) geq mathrm{val}^*(G)^{n/k}.

Our analysis exploits the novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa (ICALP 2014). We demonstrate that better communication protocols yield better parallel repetition theorems: in particular, our first theorem crucially uses a quantum search protocol by Aaronson and Ambainis, which gives a quadratic Grover speed-up for distributed search problems. Finally, our results apply to a broader class of games than were previously considered before; in particular, we obtain the first parallel repetition theorem for entangled games involving more than two players, and for games involving quantum outputs.

Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
Kai-Min Chung, Xin Li, and Xiaodi Wu . Manuscript, 2014

We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against an adversary who collects quantum side information from several initially independent classical random sources. This is a natural generalization of the two much studied problems of seeded randomness extraction against quantum side information, and classical independent source extractors. With new challenges such as potential entanglement in the side information, it is not a prior clear under what conditions do quantum multi-source extractors exist; the only previous work in this setting is [KK12], where the classical inner-product two-source extractors of [CG88] and [DEOR04] are shown to be quantum secure in the restricted Independent Adversary (IA) Model and entangled Bounded Storage (BS) Model.

In this paper we propose a new model called General Entangled (GE) Adversary Model, which allows arbitrary entanglement in the side information and subsumes both the IA model and the BS model. We proceed to show how to construct GE-secure quantum multi-source extractors. To that end, we propose another model called One-sided Adversary (OA) Model, which is weaker than all the above models. Somewhat surprisingly, we establish an equivalence between strong OA-security and strong GE-security. As a result, all classical multi-source extractors can either directly work, or be modified to work in the GE model at the cost of one extra random source. Thus, our constructions essentially match the best known constructions of classical multi-source extractors. This answers several open questions in [KK12,DPVR12].

We also apply our techniques to two important problems in cryptography and distributed computing  —  privacy amplification and network extractor. Both problems deal with converting secret weak random sources into secret uniform random bits in a communicating environment, with the presence of a passive adversary who has unlimited computational power and can see every message transmitted. We show that as long as the sources have certain amounts of conditional min-entropy in our GE model (even with entangled quantum side information), we can design very efficient privacy amplification protocols and network extractors.

Physical Randomness Extractors
Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu . Plenary talk at the 17th Conference on Quantum Information Processing (QIP 2014).

How to generate provably true randomness with minimal assumptions? This question is important not only for the efficiency and the security of information processing, but also for understanding how extremely unpredictable events are possible in Nature. All current solutions require special structures in the initial source of randomness, or a certain independence relation among two or more sources. Both types of assumptions are impossible to test and difficult to guarantee in practice. Here we show how this fundamental limit can be circumvented by extractors that base security on the validity of physical laws and extract randomness from untrusted quantum devices. In conjunction with the recent work of Miller and Shi (arXiv:1402:0489), our physical randomness extractor uses just a single and general weak source, produces an arbitrarily long and near-uniform output, with a close-to-optimal error, secure against all-powerful quantum adversaries, and tolerating a constant level of implementation imprecision. The source necessarily needs to be unpredictable to the devices, but otherwise can even be known to the adversary.

Our central technical contribution, the Equivalence Lemma, provides a general principle for proving composition security of untrusted-device protocols. It implies that unbounded randomness expansion can be achieved simply by cross-feeding any two expansion protocols. In particular, such an unbounded expansion can be made robust, which is known for the first time. Another significant implication is, it enables the secure randomness generation and key distribution using public randomness, such as that broadcast by NIST's Randomness Beacon. Our protocol also provides a method for refuting local hidden variable theories under a weak assumption on the available randomness for choosing the measurement settings.

Limits of Quantum One-way Communication by Matrix Hypercontractive Inequality
Yaoyun Shi, Xiaodi Wu, and Wei Yu . Manuscript, 2013.

An important discovery in quantum information processing is that quantum one-way communication protocols can be exponentially more efficient than classical protocols. Those extraordinary quantum advantages were demonstrated through the Hidden Matching Problem and its variants, where the underlying basic task is to determine the parity of some k=2 bits of an n bit string. We prove that for larger values of k, the quantum complexities of those problems increase exponentially from O(log n) to Omega(n^{1-2/k}), which is almost tight and renders any super-polynomial quantum-classical gaps impossible. Our results also rule out a ‘‘quantum argument’’, in the sense of Kerenidis and de Wolf (Journal of Computer and System Sciences, 69(3)395–420, 2004), for proving an exponential lower bound on Locally Decodable Codes for more than 2 queries. Our proofs are new applications of the matrix Hypercontractive Inequality developed by Ben-Aroya, Regev, and de Wolf (FOCS 2008).

Epsilon-net method for optimizations over separable states
Yaoyun Shi and Xiaodi Wu . Contributed talk at the 15th Workshop on Quantum Information Processing (QIP 2012). In the Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012). Theoretical Computer Science, 2015 .

We give algorithms for the optimization problem: max_rho mathrm{Tr}(Qrho), where Q is a Hermitian matrix, and the variable rho is a bipartite separable quantum state. This problem lies at the heart of several problems in quantum computation and information, such as the complexity of QMA(2). While the problem is NP-hard, our algorithms are better than brute force for several instances of interest. In particular, they give PSPACE upper bounds on promise problems admitting a QMA(2) protocol in which the verifier performs only logarithmic number of elementary gate on both proofs, as well as the promise problem of deciding if a bipartite local Hamiltonian has large or small ground energy. For Qge0, our algorithm runs in time exponential in |Q|_F. While the existence of such an algorithm was first proved recently by Brandao, Christandl and Yard in Proceedings of the 43rd annual ACM Symposium on Theory of Computation , 343–352, 2011, our algorithm is conceptually simpler.

Parallel approximation of min-max problems with applications to classical and quantum zero-sum games
Gus Gutoski and Xiaodi Wu . Featured talk at the 15th Workshop on Quantum Information Processing (QIP 2012). In the Proceedings of the 27rd Annual IEEE Conference on Computational Complexity (CCC 2012). Computational Complexity, 22(2):385-428, 2013, the special issue of CCC 2012.

This paper presents an efficient parallel algorithm for a new class of min-max problems based on the matrix multiplicative weights update method. Our algorithm can be used to find near-optimal strategies for competitive two-player classical or quantum games in which a referee exchanges any number of messages with one player followed by any number of additional messages with the other. This algorithm considerably extends the class of games which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for a game in which one player reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG, SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a new class of semidefinite programs whose feasible region consists of n-tuples of semidefinite matrices that satisfy a ‘‘transcript-like’’ consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.

Parallelized Solution to Semidefinite Programmings in Quantum Complexity Theory
Xiaodi Wu . Manuscript, 2010. Note: most of the techniques in this paper are applied and improved in the above paper. However, this paper contains more examples of the applications of such techniques.

In this paper we present an equilibrium value based framework for solving SDPs via the multiplicative weight update method which is different from the one in Kale's thesis [Kale07]. One of the main advantages of the new framework is that we can guarantee the convertibility from approximate to exact feasibility in a much more general class of SDPs than previous result. Another advantage is the design of the oracle which is necessary for applying the multiplicative weight update method is much simplified in the general case. This leads to an alternative and easier solutions to the SDPs used in the previous results QIP(2) subseteq PSPACE [JainUW09] and QMAM=PSPACE [JainJUW09]. Furthermore, we provide a generic form of SDPs which can be solved in the similar way. By parallelizing every step in our solution, we are able to solve a class of SDPs in NC. Although our motivation is from quantum computing, our result will also apply to any SDP which satisfies our conditions directly.

In addition to the new framework for solving SDPs, we also provide a novel framework which improves the range of equilibrium value problems that can be solved via the multiplicative weight update method. Before this work we are only able to calculate the equilibrium value where one of the two convex sets needs to be the set of density operators. Our work demonstrates that in the case when one set is the set of density operators with further linear constraints, we are still able to approximate the equilibrium value to high precision via the multiplicative weight update method.

Equilibrium Value Method for the proof of QIP=PSPACE
Xiaodi Wu . Manuscript, 2010.

We provide an alternative proof of QIP=PSPACE to the recent breakthrough result [JainJUW09]. Unlike solving some semidefinite program corresponding to the definition of the complexity class, our method starts with one QIP-complete problem which computes the diamond norm between two admissible quantum channels. The key observation is that we can convert the computation of the diamond norm into the computation of some equilibrium value, which could be interesting for its own sake. The later problem, different from semidefinite programs, is generally more structured and easier to solve. The multiplicative weight update method is also used to solve the equilibrium value problem, however, in a relatively simpler way than the original proof [JainJUW09]. Furthermore, we provide a generalized form of equilibrium value problems which can be solved in the same way as well as comparisons to semidefinite programs.

Non-Identity Check Remains QMA-Complete for Short Circuits
Zhengfeng Ji and Xiaodi Wu . Contributed talk at AQIS09 (Asian Conference on Quantum Information Science)

In the Non-Identity Check problem, we are given a quantum circuit as input, and are asked whether it is far away from the identity or not. It is well known that this problem is QMA-complete [JWB05]. In this note, it is shown that the Non-Identity Check problem remains QMA-complete for circuits of short depth. Specifically, we prove that for constant depth quantum circuit in which each gate is given to Omega(log n) bits of precision, the Non-Identity Check problem is QMA-complete. It also follows that polylog depth circuit consisting of only gates from any universal gate set is QMA-complete.

Exact Quantum Search by Parallel Unitary Discrimination Schemes
(by contribution) Xiaodi Wu and Runyao Duan. Physical Review A, 78, 012303 (2008). Selected for the July 2008 issue of Virtual Journal of Quantum Information.

We study the unsorted database search problem with items N from the viewpoint of unitary discrimination. Instead of considering the famous O(sqrt{N}) Grover's the bounded-error algorithm for the original problem, we seek for the results about the exact algorithms, i.e. the ones succeed with certainty. Under the standard oracle model sum_j (-1)^{delta_{tau j}}|jranglelangle j|, we demonstrate a tight lower bound frac{2}{3}N+o(N) of the number of queries for any parallel scheme with unentangled input states. With the assistance of entanglement, we obtain a general lower bound frac{1}{2}(N-sqrt{N}). We provide concrete examples to illustrate our results. In particular, we show that the case of N=6 can be solved exactly with only two queries by using a bipartite entangled input state. Our results indicate that in the standard oracle model the complexity of exact quantum search with one unique solution can be strictly less than that of the calculation of OR function.

Verifier-based Algorithm for Unsorted Database Search Problem
(by contribution) Xiaodi Wu and Gui Lu Long. International Journal of Quantum Information, vol.5 no.4, pp 597 - 604 (2007)

Unsorted database search problem is an important science and engineering problem. We proposed quantum algorithm to solve the problem by dividing the database binarily and then use a probabilistic verifier algorithm to determine if the item is within one part of the divided database. We analyzed the computational complexity of this algorithm, and found that in general, the number of steps is proportional to that in the standard Grover algorithm. However in some cases, it is less than that of the Grover algorithm.

Data Processing and software realization of wave-lengths of spectrum during CCD measurement (in Chinese)
(by contribution) Xiaodi Wu, Yong-tao Huang and Xin-kun Ma. Experimental Technology and Management, vol. 24, no. 4 p48-51 (2006)