



02263nas a2200145   4500008004100000245006800041210006700109260001400176520182500190100001902015700001202034700001902046700001502065856003702080       2020                        eng d00aConstant-round Blind Classical Verification of Quantum Sampling0 aConstantround Blind Classical Verification of Quantum Sampling  c12/8/20203 a<p>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&isin;{0,1}n and a quantum circuit C, and the goal of the classical client is to learn a sample from the output z&larr;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.</p>1 aChung, Kai-Min1 aLee, Yi1 aLin, Han-Hsuan1 aWu, Xiaodi  uhttps://arxiv.org/abs/2012.0484801895nas a2200157   4500008004100000245004900041210004800090260001500138520145500153100001801608700001901626700001801645700002201663700001501685856003701700       2017                        eng d00aComputational Notions of Quantum Min-Entropy0 aComputational Notions of Quantum MinEntropy  c2017/09/093 a<p>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 &minus; ℓ conditioned on an ℓ- 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.</p>1 aChen, Yi-Hsiu1 aChung, Kai-Min1 aLai, Ching-Yi1 aVadhan, Salil, P.1 aWu, Xiaodi  uhttps://arxiv.org/abs/1704.07309