检索结果-内蒙古大学图书馆

Variational learning algorithms for quantum query complexity

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Wu, Zipeng Hou, Shi-Yao Zhang, Chao Li, Lvzhou Zeng, Bei Department of Physics The Hong Kong University of Science and Technology Clear Water Bay Kowloon Hong Kong College of Physics and Electronic Engineering Center for Computational Sciences Sichuan Normal University Chengdu610068 China Shenzhen SpinQ Technology Co. Ltd. Shenzhen China Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

Quantum query complexity is pivotal in the analysis of quantum algorithms, encompassing wellknown examples like search and period-finding algorithms. These algorithms typically involve a sequence of unitary operations and oracle calls dependent on an input variable. In this study, we introduce a variational learning approach to explore quantum query complexity. Our method employs an efficient parameterization of the unitary operations and utilizes a loss function derived from the algorithm's error probability. We apply this technique to various quantum query complexities, notably devising a new algorithm that resolves the 5-bit Hamming modulo problem with four queries, addressing an open question from arXiv:2112.14682. This finding is corroborated by a Semidefinite Programming (SDP) approach. Our numerical method exhibits superior memory efficiency compared to SDP and can identify quantum query algorithms that require a smaller workspace register dimension, an aspect not optimized by SDP. These advancements present a significant step forward in the practical application and understanding of quantum query algorithms. Copyright © 2022, The Authors. All rights reserved.

关键词： Learning algorithms

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Zadik, Ilias Song, Min Jae Wein, Alexander S. Bruna, Joan Department of Mathematics Massachusetts Institute of Technology United States Courant Institute of Mathematical Sciences New York University United States Simons Institute for the Theory of Computing UC Berkeley United States Center for Data Science New York University United States Center for Computational Mathematics Flatiron Institute United States

Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canonical task of clustering d-dimensional Gaussian mixtures with unknown (and possibly degenerate) covariance. Recent works (Ghosh et al.'20;Mao, Wein'21;Davis, Diaz, Wang'21) have established lower bounds against the class of low-degree polynomial methods and the sum-of-squares (SoS) hierarchy for recovering certain hidden structures planted in Gaussian clustering instances. Prior work on many similar inference tasks portends that such lower bounds strongly suggest the presence of an inherent statistical-to-computational gap for clustering, that is, a parameter regime where the clustering task is statistically possible but no polynomial-time algorithm succeeds. One special case of the clustering task we consider is equivalent to the problem of finding a planted hypercube vector in an otherwise random subspace. We show that, perhaps surprisingly, this particular clustering model does not exhibit a statistical-to-computational gap, despite the aforementioned low-degree and SoS lower bounds. To achieve this, we give an algorithm based on Lenstra-Lenstra-Lovász lattice basis reduction which achieves the statistically-optimal sample complexity of d + 1 samples. This result extends the class of problems whose conjectured statistical-to-computational gaps can be "closed" by "brittle" polynomial-time algorithms, highlighting the crucial but subtle role of noise in the onset of statistical-to-computational gaps. Copyright © 2021, The Authors. All rights reserved.

关键词： Polynomial approximation

LightXML: Transformer with dynamic negative sampling for high-performance extreme multi-label text classification

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Jiang, Ting Wang, Deqing Sun, Leilei Yang, Huayi Zhao, Zhengyang Zhuang, Fuzhen SKLSDE and BDBC Lab Beihang University Beijing China Key Lab of Intelligent Information Processing of CAS Institute of Computing Technology CAS Beijing China Beijing Advanced Innovation Center for Imaging Theory and Technology Academy for Multidisciplinary Studies Capital Normal University Beijing China

Extreme Multi-label text Classification (XMC) is a task of finding the most relevant labels from a large label set. Nowadays deep learning-based methods have shown significant success in XMC. However, the existing methods (e.g., AttentionXML and X-Transformer etc) still suffer from 1) combining several models to train and predict for one dataset, and 2) sampling negative labels statically during the process of training label ranking model, which reduces both the efficiency and accuracy of the model. To address the above problems, we proposed LightXML, which adopts end-to-end training and dynamic negative labels sampling. In LightXML, we use generative cooperative networks to recall and rank labels, in which label recalling part generates negative and positive labels, and label ranking part distinguishes positive labels from these labels. Through these networks, negative labels are sampled dynamically during label ranking part training by feeding with the same text representation. Extensive experiments show that LightXML outperforms state-of-the-art methods in five extreme multi-label datasets with much smaller model size and lower computational complexity. In particular, on the Amazon dataset with 670K labels, LightXML can reduce the model size up to 72% compared to AttentionXML. Our code is available at http://***/kongds/LightXML. Copyright © 2021, The Authors. All rights reserved.

关键词： Deep learning

Improved Approximation Algorithms for Bounded-Degree Local Hamiltonians

学校读者我要写书评

暂无评论

Physical Review Letters 2021年第25期127卷 250502-250502页

作者： Anurag Anshu David Gosset Karen J. Morenz Korol Mehdi Soleimanifar Department of EECS & Challenge Institute for Quantum Computation University of California Berkeley California 94720 USA and Simons Institute for the Theory of Computing Berkeley California 94720 USA Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Waterloo N2L 3G1 Canada Perimeter Institute for Theoretical Physics Waterloo N2L 2Y5 Canada Department of Chemistry University of Toronto Toronto M5S 3H6 Canada Center for Theoretical Physics Massachusetts Institute of Technology Cambridge 02139 USA

The low-temperature properties of interacting quantum systems are believed to require exponential resources to compute in the general case. Quantifying the extent to which such properties can be approximated using efficient algorithms remains a significant open challenge. Here, we consider the task of approximating the ground state energy of two-local quantum Hamiltonians with bounded-degree interaction graphs. Most existing algorithms optimize the energy over the set of product states. We propose and analyze a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an n-qubit product state with variance Var and improves its energy by an amount proportional to Var2/n. In a typical case, this results in an extensive improvement in the estimated energy. We extend our results to k-local Hamiltonians and entangled initial states.

关键词： Quantum algorithms Quantum simulation

High-Order Randomized Compiler for Hamiltonian Simulation

学校读者我要写书评

暂无评论

PRX Quantum 2024年第2期5卷 020330-020330页

作者： Kouhei Nakaji Mohsen Bagherimehrab Alán Aspuru-Guzik Chemical Physics Theory Group Department of Chemistry University of Toronto Toronto Ontario Canada M5S 3H6 Research Center for Emerging Computing Technologies National Institute of Advanced Industrial Science and Technology (AIST) 1-1-1 Umezono Tsukuba Ibaraki 305-8568 Japan Quantum Computing Center Keio University 3-14-1 Hiyoshi Kohoku-ku Yokohama Kanagawa 223-8522 Japan Department of Computer Science University of Toronto Toronto Ontario Canada M5S 2E4 Vector Institute for Artificial Intelligence Toronto Ontario Canada M5G 1M1 Department of Chemical Engineering & Applied Chemistry University of Toronto Toronto Ontario Canada M5S 3E5 Department of Materials Science & Engineering University of Toronto Toronto Ontario Canada M5S 3E4 Canadian Institute for Advanced Research (CIFAR) Toronto Ontario Canada M5S 1M1

Hamiltonian simulation is known to be one of the fundamental building blocks of a variety of quantum algorithms such as its most immediate application, that of simulating many-body systems to extract their physical properties. In this work, we present qSWIFT, a high-order randomized algorithm for Hamiltonian simulation. In qSWIFT, the required number of gates for a given precision is independent of the number of terms in the Hamiltonian, while the systematic error is exponentially reduced with regard to the order parameter. In this respect, our qSWIFT is a higher-order counterpart of the previously proposed quantum stochastic drift protocol (qDRIFT), the number of gates in which scales linearly with the inverse of the precision required. We construct the qSWIFT channel and establish a rigorous bound for the systematic error quantified by the diamond norm. qSWIFT provides an algorithm to estimate given physical quantities by using a system with one ancilla qubit, which is as simple as other product-formula-based approaches such as regular Trotter-Suzuki decompositions and qDRIFT. Our numerical experiment reveals that the required number of gates in qSWIFT is significantly reduced compared to qDRIFT. In particular, the advantage is significant for problems where high precision is required; e.g., to achieve a systematic relative propagation error of 10−6, the required number of gates in third-order qSWIFT is 1000 times smaller than that of qDRIFT.

关键词： Quantum computation Quantum simulation

Spinfoam on a Lefschetz thimble: Markov chain Monte Carlo computation of a Lorentzian spinfoam propagator

学校读者我要写书评

暂无评论

Physical Review D 2021年第8期103卷 084026-084026页

作者： Muxin Han Zichang Huang Hongguang Liu Dongxue Qu Yidun Wan State Key Laboratory of Surface Physics Fudan University Shanghai 200433 China Department of Physics Center for Field Theory and Particle Physics Institute for Nanoelectronic devices and Quantum computing Fudan University Shanghai 200433 China and Department of Physics and Institute for Quantum Science and Engineering Southern University of Science and Technology Shenzhen 518055 China

We compute numerically the Lorentzian Engle-Pereira-Rovelli-Livine spinfoam propagator on a 4-simplex, by adapting the Lefschetz thimble and Markov chain Monte-Carlo methods to oscillatory spinfoam integrals. Our method can compute any spinfoam observables at relatively large spins. We obtain the numerical results of the propagators at different spins and demonstrate their consistency with the expected spinfoam semiclassical behavior in the large spin limit. Our results exhibit significant quantum corrections at smaller spins. Our method is reliable and thus can be employed to discover the semiclassical and quantum behaviors of the spinfoam model.

关键词： Loop quantum gravity

On the smallest singular value of symmetric random matrices

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Jain, Vishesh Sah, Ashwin Sawhney, Mehtaab Simons Institute for the Theory of Computing BerkeleyCA94720 United States Department of Mathematics Massachusetts Institute of Technology CambridgeMA02139 United States

We show that for an n × n random symmetric matrix An, whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable ξ with mean 0 and variance 1, P[sn(An) ≤ ǫ/√n] ≤ Oξ(ǫ1/8 + exp(−Ωξ(n1/2))) for all ǫ ≥ 0. This improves a result of Vershynin, who obtained such a bound with n1/2 replaced by nc for a small constant c, and 1/8 replaced by (1/8) + η (with implicit constants also depending on η > 0). Furthermore, when ξ is a Rademacher random variable, we prove that P[sn(An) ≤ ǫ/√n] ≤ O(ǫ1/8 + exp(−Ω((log n)1/4n1/2))) for all ǫ ≥ 0. The special case ǫ = 0 improves a recent result of Campos, Mattos, Morris, and Morrison, which showed that P[sn(An) = 0] ≤ O(exp(−Ω(n1/2))). The main innovation in our work are new notions of arithmetic structure – the Median Regularized Least Common Denominator and the Median Threshold, which we believe should be more generally useful in contexts where one needs to combine anticoncentration information of different parts of a vector. Copyright © 2020, The Authors. All rights reserved.

关键词： Random variables

On the smoothed analysis of the smallest singular value with discrete noise

学校读者我要写书评

暂无评论

arXiv 2020年

Let A be an n × n real matrix, and let M be an n × n random matrix whose entries are i.i.d sub-Gaussian random variables with mean 0 and variance 1. We make two contributions to the study of sn(A + M), the smallest singular value of A + M. (1) We show that for all ϵ ≥ 0, [sn(A + M) ≤ ϵ] = O(ϵ√n) + 2e−Ω(n), provided only that A has Ω(n) singular values which are O(√n). This extends a well-known result of Rudelson and Vershynin, which requires all singular values of A to be O(√n). (2) We show that any bound of the form (Formula presented) must have C3 = Ω(C1√C2). This complements a result of Tao and Vu, who proved such a bound with C3 = O(C1C2 + C1 + 1), and counters their speculation of possibly taking C3 = O(C1 + C2). Copyright © 2020, The Authors. All rights reserved.

关键词： Machine learning

Optimal and algorithmic norm regularization of random matrices

学校读者我要写书评

暂无评论

arXiv 2020年

Let A be an n × n random matrix whose entries are i.i.d. with mean 0 and variance 1. We present a deterministic polynomial time algorithm which, with probability at least 1 − 2 exp(−Ω(ǫn)) in the choice of A, finds an ǫn × ǫn sub-matrix such that zeroing it out results in Ae with (formula presented). Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for A a symmetric n × n random matrix whose upper-diagonal entries are i.i.d. with mean 0 and variance 1. © 2020, CC BY.

关键词： Polynomial approximation