02263nas a2200145 4500008004100000245006800041210006700109260001400176520182500190100001902015700001202034700001902046700001502065856003702080 2020 eng d00aConstant-round Blind Classical Verification of Quantum Sampling0 aConstantround Blind Classical Verification of Quantum Sampling c12/8/20203 a

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'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'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.

1 aChung, Kai-Min1 aLee, Yi1 aLin, Han-Hsuan1 aWu, Xiaodi uhttps://arxiv.org/abs/2012.0484802222nas a2200169 4500008004100000245010800041210006900149260001400218520167700232100001801909700001901927700001701946700001901963700001501982700001801997856003702015 2020 eng d00aSampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning0 aSamplingbased sublinear lowrank matrix arithmetic framework for  c6/18/20203 a

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation systems [STOC'19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC'19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

1 aChia, Nai-Hui1 aGilyen, Andras1 aLi, Tongyang1 aLin, Han-Hsuan1 aTang, Ewin1 aWang, Chunhao uhttps://arxiv.org/abs/1910.0615102281nas a2200133 4500008004100000245012600041210006900167520180200236100001802038700001702056700001902073700001802092856003702110 2019 eng d00aQuantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches0 aQuantuminspired classical sublineartime algorithm for solving lo3 a

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with m constraint matrices, each of dimension n and rank poly(logn), our algorithm gives a succinct description and any entry of the solution matrix in time O(m⋅poly(logn,1/ε)) given access to a sample-based low-overhead data structure of the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms. The cost of solving SDPs by MMW mainly comes from the exponentiation of Hermitian matrices, and we propose two new technical ingredients (compared to previous sample-based algorithms) for this task that may be of independent interest: ∙ Weighted sampling: assuming sampling access to each individual constraint matrix A1,…,Aτ, we propose a procedure that gives a good approximation of A=A1+⋯+Aτ. ∙ Symmetric approximation: we propose a sampling procedure that gives low-rank spectral decomposition of a Hermitian matrix A. This improves upon previous sampling procedures that only give low-rank singular value decompositions, losing the signs of eigenvalues.

1 aChia, Nai-Hui1 aLi, Tongyang1 aLin, Han-Hsuan1 aWang, Chunhao uhttps://arxiv.org/abs/1901.0325401487nas a2200145 4500008004100000245009000041210006900131260001500200300000900215490000700224520101500231100002401246700001901270856005201289 2016 eng d00aUpper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester0 aUpper bounds on quantum query complexity inspired by the Elitzur c2016/11/28 a1-350 v123 a

Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], we introduce a new query complexity model, which we call bomb query complexity $B(f)$. We investigate its relationship with the usual quantum query complexity $Q(f)$, and show that $B(f)=\Theta(Q(f)^2)$. This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on $Q(f)=\Theta(\sqrt{B(f)})$. We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with $O(n^{1.5})$ quantum query complexity, improving the best known algorithm of $O(n^{1.5}\sqrt{\log n})$ [arXiv:quant-ph/0606127]. Applying this method to the maximum bipartite matching problem gives an $O(n^{1.75})$ algorithm, improving the best known trivial $O(n^2)$ upper bound.

1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan uhttp://theoryofcomputing.org/articles/v012a018/01035nas a2200181 4500008004100000020002200041022001400063245002300077210002300100260001500123300000900138490000700147520060100154100001900755700002400774700001900798856003600817 2015 eng d a978-3-939897-96-5 a1868-896900aOracles with Costs0 aOracles with Costs c2015/02/07 a1-260 v443 a While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal. 1 aKimmel, Shelby1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan uhttp://arxiv.org/abs/1502.0217401142nas a2200157 4500008004100000245008300041210006900124260001500193520063900208100002300847700001800870700002400888700001900912700001600931856003700947 2014 eng d00aDifferent Strategies for Optimization Using the Quantum Adiabatic Algorithm 0 aDifferent Strategies for Optimization Using the Quantum Adiabati c2014/01/283 a We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution. 1 aCrosson, Elizabeth1 aFarhi, Edward1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan1 aShor, Peter uhttp://arxiv.org/abs/1401.7320v1