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

On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Grochow, Joshua A. Qiao, Youming Departments of Computer Science and Mathematics University of Colorado Boulder United States Centre for Quantum Software and Information University of Technology Sydney Australia

Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introduction of the complexity class TI (Grochow & Qiao, SIAM J. Comp.’23 & ITCS’21). Using the tensorial viewpoint, Grochow & Qiao (ACM Trans. Comput. theory,’24 & CCC’21) gave moderately exponential-time search- and counting-to-decision reductions for some class of p-groups. A significant issue was that the reductions usually incurred a quadratic increase in the length of the tensors involved. When the tensors represent p-groups, this corresponds to an increase in the order of the group of the form |G|Θ(log |G|), negating any gains in the Cayley table model. In this paper, we present a new kind of tensor gadget that allows us to replace those quadratic-length reductions with linear-length ones, yielding the following consequences: 1. If Graph Isomorphism is in P, then testing equivalence of cubic forms in n variables over Fq, and testing isomorphism of n-dimensional algebras over Fq, can both be solved in time qO(n), improving from the brute-force upper bound qO(n2) for both of these. 2. Combined with the |G|O((log |G|)5/6)-time isomorphism-test for p-groups of class 2 and exponent p (Sun, STOC’23), our reductions extend this runtime to p-groups of class c and exponent p where c O(n1.8·log q) for cubic form equivalence and algebra isomorphism. 3. Polynomial-time search- and counting-to-decision reduction for testing isomorphism of p-groups of class 2 and exponent p when Cayley tables are given. This answers questions of Arvind and Tóran (Bull. EATCS, 2005) for this group class, thought to be one of the hardest cases of Group Isomorphism. Our reductions are presented in a more modular and composable fashion compared to previous gadgets, making them easier to reason about and, crucially, easier to combine. The results are also used by Ivanyos–Mendoza–Qiao–Sun–Zhang to simplify the algorithm in (S

关键词： Tensors

Numerical methods for rectangular multiparameter eigenvalue problems, with applications to finding optimal ARMA and LTI models

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Hochstenbach, Michiel E. Košir, Tomaž Plestenjak, Bor Department of Mathematics and Computer Science TU Eindhoven PO Box 513 5600 MB Netherlands Faculty of Mathematics and Physics University of Ljubljana Jadranska 19 LjubljanaSI-1000 Slovenia

Standard multiparameter eigenvalue problems (MEPs) are systems of k ≥ 2 linear kparameter square matrix pencils. Recently, a new form of multiparameter eigenvalue problems has emerged: a rectangular MEP (RMEP) with only one multivariate rectangular matrix pencil, where we are looking for combinations of the parameters for which the rank of the pencil is not full. applications include finding the optimal least squares autoregressive moving average (ARMA) model and the optimal least squares realization of autonomous linear time-invariant (LTI) dynamical system. For linear and polynomial RMEPs, we give the number of solutions and show how these problems can be solved numerically by a transformation into a standard MEP. For the transformation we provide new linearizations for quadratic multivariate matrix polynomials with a specific structure of monomials and consider mixed systems of rectangular and square multivariate matrix polynomials. This numerical approach seems computationally considerably more attractive than the block Macaulay method, the only other currently available numerical method for polynomial *** Codes 65F15, 15A18, 15A22, 65F50, 93B15 Copyright © 2022, The Authors. All rights reserved.

关键词： Matrix algebra

Fundamental causal bounds of quantum random access memories

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Wang, Yunfei Alexeev, Yuri Jiang, Liang Chong, Frederic T. Liu, Junyu Martin A. Fisher School of Physics Brandeis University WalthamMA02453 United States Computational Science Division Argonne National Laboratory LemontIL60439 United States Chicago Quantum Exchange ChicagoIL60637 United States Department of Computer Science The University of Chicago ChicagoIL60637 United States Pritzker School of Molecular Engineering The University of Chicago ChicagoIL60637 United States Kadanoff Center for Theoretical Physics The University of Chicago ChicagoIL60637 United States qBraid Co. ChicagoIL60615 United States SeQure ChicagoIL60615 United States

Quantum devices should operate in adherence to quantum physics principles. Quantum random access memory (QRAM), a fundamental component of many essential quantum algorithms for tasks such as linear algebra, data search, and machine learning, is often proposed to offer O(log N) circuit depth for O(N) data size, given N qubits. However, this claim appears to breach the principle of relativity when dealing with a large number of qubits in quantum materials interacting locally. In our study we critically explore the intrinsic bounds of rapid quantum memories based on causality, employing the relativistic quantum field theory and Lieb–Robinson bounds in quantum many-body systems. In this paper, we consider a hardware-efficient QRAM design in hybrid quantum acoustic systems. Assuming clock cycle times of approximately 10−3 seconds and a lattice spacing of about 1 micrometer, we show that QRAM can accommodate up to O(107) logical qubits in 1 dimension, O(1015) to O(1020) in various 2D architectures, and O(1024) in 3 dimensions. We contend that this causality bound broadly applies to other quantum hardware systems. Our findings highlight the impact of fundamental quantum physics constraints on the long-term performance of quantum computing applications in data science and suggest potential quantum memory designs for performance enhancement. Copyright © 2023, The Authors. All rights reserved.

关键词： Linear algebra

Subresultant of several univariate polynomials

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Hong, Hoon Yang, Jing Department of Mathematics North Carolina State University Box 8205 RaleighNC27695 United States SMS-HCIC School of Mathematics and Physics Guangxi Minzu University Nanning530006 China

Subresultant of two univariate polynomials is a fundamental object in computational algebra and geometry with many applications (for instance, parametric GCD and parametric multiplicity of roots). In this paper, we generalize the theory of subresultants of two polynomials to arbitrary number of polynomials, resulting in multi-polynomial subresultants. Specifically, 1. we propose a definition of multi-polynomial subresultants, which is an expression in terms of roots;2. we illustrate the usefulness of the proposed definition via the following two fundamental applications: • parametric GCD of multi-polynomials, and • parametric multiplicity of roots of a polynomial;3. we provide several expressions for the multi-polynomials subresultants in terms of coefficients, for computation. © 2021, CC BY.

关键词： polynomials

Sparse tensor algebra compilation

学校读者我要写书评

暂无评论

Sparse tensor algebra compilation

作者： Kjølstad, Fredrik Berg. Massachusetts Institute of Technology

学位级别：博士

This dissertation shows how to compile any sparse tensor algebra expression to CPU and GPU code that matches the performance of hand-optimized implementations. A tensor algebra expression is sparse if at least one of its tensor operands is sparse, and a tensor is sparse if most of its values are zero. If a tensor is sparse, then we can store its nonzero values in a compressed data structure, and omit the zeros. Indeed, as the matrices and tensors in many important applications are extremely sparse, compressed data structures provide the only practical means to store them. A sparse tensor algebra expression may contain any number of operations, which must be compiled to fused loops that compute the entire expression simultaneously. It is not viable to support only binary expressions, because their composition may result in worse asymptotic complexity than the fused implementation. I present compiler techniques to generate fused loops that coiterate over any number of tensors stored in different types of data structures. By design, these loops avoid computing values known to be zero due to the algebraic properties of their operators. Sparse tensor algebra compilation is made possible by a sparse iteration theory that formulates sparse iteration spaces as set expressions of the coordinates of nonzero values. By ordering iteration space dimensions hierarchically, the compiler recursively generates loops that coiterate over tensor data structures one dimension at a time. By organizing per-dimension coiteration into regions based on algebraic operator properties, it removes operations that will result in zero. And by transforming the sparse iteration spaces, it optimizes the generated code. The result is the first sparse iteration compiler, called the Tensor algebra Compiler (taco). Taco can compile any tensor algebra expressions, with tensors stored in different types of sparse and dense data structures, to code that matches the performance of hand-optimized implementati

关键词： Electrical Engineering and computer Science

algebra-Based Loop Synthesis 16th

学校读者我要写书评

暂无评论

Algebra-Based Loop Synthesis

16th International Conference on Integrated Formal Methods (IFM)

作者： Humenberger, Andreas Bjorner, Nikolaj Kovacs, Laura TU Wien Vienna Austria Microsoft Res Redmond WA USA

ISBN: (纸本)9783030634612;9783030634605

We present a method for synthesizing loops over affine assignments from polynomial invariants. It is complete when the number of auxiliary variables is bounded, thus serving as a foundation for strength reduction optimization that convert polynomial expressions into incremental affine computations. Our work has applications towards synthesizing loops satisfying a given polynomial loop invariant, program verification, as well as generating number sequences from algebraic relations. To understand viability of the methodology and heuristics for synthesizing loops with a large number of auxiliary variables, we implement and evaluate the method using the Absynth tool.

关键词： polynomials

Fast quantum algorithm for differential equations

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bagherimehrab, Mohsen Nakaji, Kouhei Wiebe, Nathan Aspuru-Guzik, Alán Chemical Physics Theory Group Department of Chemistry University of Toronto TorontoON Canada Department of Computer Science University of Toronto TorontoON Canada 1-1-1 Umezono Ibaraki Tsukuba305-8568 Japan Quantum Computing Center Keio University 3-14-1 Hiyoshi Kohoku-ku Kanagawa Yokohama223-8522 Japan Pacific Northwest National Laboratory RichlandWA United States Canadian Institute for Advanced Research TorontoON Canada Vector Institute for Artificial Intelligence TorontoON Canada Department of Chemical Engineering & Applied Chemistry University of Toronto TorontoON Canada Department of Materials Science & Engineering University of Toronto TorontoON Canada

Partial differential equations (PDEs) are ubiquitous in science and engineering. Prior quantum algorithms for solving the system of linear algebraic equations obtained from discretizing a PDE have a computational complexity that scales at least linearly with the condition number κ of the matrices involved in the computation. For many practical applications, κ scales polynomially with the size N of the matrices, rendering a polynomial-in-N complexity for these algorithms. Here we present a quantum algorithm with a complexity that is polylogarithmic in N but is independent of κ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution. Central to our methodology is using a wavelet basis as an auxiliary system of coordinates in which the condition number of associated matrices is independent of N by a simple diagonal preconditioner. We present numerical simulations showing the effect of the wavelet preconditioner for several differential equations. Our work could provide a practical way to boost the performance of quantum-simulation algorithms where standard methods are used for discretization. © 2023, CC BY.

关键词： Matrix algebra

Rewriting theory for the Life Sciences: A Unifying theory of CTMC Semantics 13th

学校读者我要写书评

暂无评论

Rewriting Theory for the Life Sciences: A Unifying Theory of...

13th International Conference on Graph Transformation (ICGT) Held as Part of Conference on Software Technologies - applications and Foundations (STAF)

作者： Behr, Nicolas Krivine, Jean Univ Paris CRI INSERM U1284 8-10 Rue Charles V F-75004 Paris France Univ Paris CNRS UMR 8243 IRIF 8 Pl Aurelie Nemours F-75205 Paris 13 France

ISBN: (纸本)9783030513726;9783030513719

The Kappa biochemistry and the MOD organo-chemistry frameworks are amongst the most intensely developed applications of rewriting theoretical methods in the life sciences to date. A typical feature of these types of rewriting theories is the necessity to implement certain structural constraints on the objects to be rewritten (a protein is empirically found to have a certain signature of sites, a carbon atom can form at most four bonds, ...). In this paper, we contribute to the theoretical foundations of these types of rewriting theory a number of conceptual and technical developments that permit to implement a universal theory of continuous-time Markov chains (CTMCs) for stochastic rewriting systems. Our core mathematical concepts are a novel rule algebra construction for the relevant setting of rewriting rules with conditions, both in Double- and in Sesqui-Pushout semantics, augmented by a suitable stochastic mechanics formalism extension that permits to derive dynamical evolution equations for pattern-counting statistics.

关键词： Double-pushout rewriting Sesqui-pushout rewriting Rule algebra Stochastic mechanics Biochemistry Organic chemistry

Review of Recent Systems for Detecting and Diagnosing Pronunciation Errors

学校读者我要写书评

暂无评论

Review of Recent Systems for Detecting and Diagnosing Pronun...

International Conference on Advanced Systems and Electric Technologies (IC_ASET)

作者： Karim Dabbabi Abdelkarim Mars Faculty of Sciences of Tunis Research Unite of Analysis and Processing of Electrical and Energetic Systems Tunis Tunisia Research Laboratory in Algebra Number Theory and Intelligent Systems Faculty of Sciences of Monastir Monastir Tunisia

Nowadays, computer Aided Language Learning (CALL) frameworks have attracted a lot of attention because of their capability, adaptability, and flexibility in improving people's language skills. The field of Mispronunciation Detection and Diagnosis (MDD) is considered one of the applications of these frameworks and has recently benefited from the rapid innovation spawned in deep learning models and different acoustic, phonetic, and linguistic features. The various manner of combinations of different features and deep learning architectures for different MDD systems require huge amount of annotated textual data to be pretrained and hence achieved good performances. However, providing a large amount of annotated textual data for pre-training is a tedious and time-consuming operation. For this, a pre-trained acoustic model from unannotated data can be a good alternative. In this article, we present different MDD systems categorized according to the pre-training mode: pre-trained approaches without annotated text data and pre-trained approaches with annotated text data. Experimental results, advantages, disadvantages and additional improvements for each method explored for each category are presented and discussed.

关键词：