Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles
Ontology highlight
ABSTRACT:
SUBMITTER: Pulina L
PROVIDER: S-EPMC7326541 | biostudies-literature | 2020 Jun
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Hyperentangled states, entangled states with more than one degree of freedom, are considered as promising resource in quantum computation. Here we present a hyperparallel quantum algorithm for matrix multiplication with time complexity O(N(2)), which is better than the best known classical algorithm. In our scheme, an N dimensional vector is mapped to the state of a single source, which is separated to N paths. With the assistance of hyperentangled states, the inner product of two vectors can be calculated with a time complexity independent of dimension N. Our algorithm shows that hyperparallel quantum computation may provide a useful tool in quantum machine learning and "big data" analysis.
| S-EPMC4850379 | biostudies-other
Project description:Improving the efficiency of algorithms for fundamental computations can have a widespread impact, as it can affect the overall speed of a large amount of computations. Matrix multiplication is one such primitive task, occurring in many systems-from neural networks to scientific computing routines. The automatic discovery of algorithms using machine learning offers the prospect of reaching beyond human intuition and outperforming the current best human-designed algorithms. However, automating the algorithm discovery procedure is intricate, as the space of possible algorithms is enormous. Here we report a deep reinforcement learning approach based on AlphaZero1 for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. Our agent, AlphaTensor, is trained to play a single-player game where the objective is finding tensor decompositions within a finite factor space. AlphaTensor discovered algorithms that outperform the state-of-the-art complexity for many matrix sizes. Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor's algorithm improves on Strassen's two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago2. We further showcase the flexibility of AlphaTensor through different use-cases: algorithms with state-of-the-art complexity for structured matrix multiplication and improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware. Our results highlight AlphaTensor's ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria.
| S-EPMC9534758 | biostudies-literature
Project description:Deep-focus earthquakes that occur at 350-660 km are assumed to be caused by olivine → spinel phase transformation (PT). However, there are many existing puzzles: (a) What are the mechanisms for jump from geological 10-17 - 10-15 s-1 to seismic 10 - 103 s-1 strain rates? Is it possible without PT? (b) How does metastable olivine, which does not completely transform to spinel for over a million years, suddenly transform during seconds? (c) How to connect shear-dominated seismic signals with volume-change-dominated PT strain? Here, we introduce a combination of several novel concepts that resolve the above puzzles quantitatively. We treat the transformation in olivine like plastic strain-induced (instead of pressure/stress-induced) and find an analytical 3D solution for coupled deformation-transformation-heating in a shear band. This solution predicts conditions for severe (singular) transformation-induced plasticity (TRIP) and self-blown-up deformation-transformation-heating process due to positive thermomechanochemical feedback between TRIP and strain-induced transformation. This process leads to temperature in a band, above which the self-blown-up shear-heating process in the shear band occurs after finishing the PT. Our findings change the main concepts in studying the initiation of the deep-focus earthquakes and PTs during plastic flow in geophysics in general.
| S-EPMC9588062 | biostudies-literature
Project description:The Chain Matrix Multiplication Problem (CMMP) is an optimization problem that helps to find the optimal way of parenthesization for Chain Matrix Multiplication (CMM). This problem arises in various scientific applications such as in electronics, robotics, mathematical programing, and cryptography. For CMMP the researchers have proposed various techniques such as dynamic approach, arithmetic approach, and sequential multiplication. However, these techniques are deficient for providing optimal results for CMMP in terms of computational time and significant amount of scalar multiplication. In this article, we proposed a new model to minimize the Chain Matrix Multiplication (CMM) operations based on group counseling optimizer (GCO). Our experimental results and their analysis show that the proposed GCO model has achieved significant reduction of time with efficient speed when compared with sequential chain matrix multiplication approach. The proposed model provides good performance and reduces the multiplication operations varying from 45% to 96% when compared with sequential multiplication. Moreover, we evaluate our results with the best known dynamic programing and arithmetic multiplication approaches, which clearly demonstrate that proposed model outperforms in terms of computational time and space complexity.
| S-EPMC7959611 | biostudies-literature
Project description:Pure strategy board games such as chess are popular intellectual activities, and solving them is a challenging task in computer science. In addition to traditional games, many new board games have gained popularity in recent years. Ostle is one such unsolved game published in 2017. It is based on simple rules but is highly competitive. It is a two-player zero-sum game with perfect information in which the game-theoretical values of all game states can be obtained. In this study, we strongly solved Ostle by retrograde analysis. Utilizing various known techniques, including bitboards and succinct indexable dictionaries, significantly reduced the memory consumption in the analyses. We confirmed that the initial position is a draw and found some fundamental properties of Ostle. Additionally, we manually composed a tactical Ostle puzzle with the help of extracted outputs of the analyses. The result demonstrates that solving recent games provided helpful information to compose high-quality problems.
| S-EPMC10557503 | biostudies-literature
Project description:Chagas disease is the highest impact parasitic disease in the Americas, yet remains virtually unknown and untreated, despite the fact that the infection is curable and the global problem of Chagas disease is manageable. The causes of this situation and how it can be changed are the focus of this communication.
| S-EPMC5748248 | biostudies-literature
Project description:We present a first-principles approach to electronic many-body systems strongly coupled to cavity modes in terms of matter-photon one-body reduced density matrices. The theory is fundamentally nonperturbative and thus captures not only the effects of correlated electronic systems but accounts also for strong interactions between matter and photon degrees of freedom. We do so by introducing a higher-dimensional auxiliary system that maps the coupled fermion-boson system to a dressed fermionic problem. This reformulation allows us to overcome many fundamental challenges of density-matrix theory in the context of coupled fermion-boson systems and we can employ conventional reduced density-matrix functional theory developed for purely fermionic systems. We provide results for one-dimensional model systems in real space and show that simple density-matrix approximations are accurate from the weak to the deep-strong coupling regime. This justifies the application of our method to systems that are too complex for exact calculations and we present first results, which show that the influence of the photon field depends sensitively on the details of the electronic structure.
| S-EPMC6875895 | biostudies-literature
Project description:As a particular case study of the formal verification of state-of-the-art, real software, we discuss the specification and verification of a corrected version of the implementation of a linked list as provided by the Java Collection framework.
| S-EPMC7480693 | biostudies-literature
Project description:We show that n thermal fermionic alkaline-earth-metal atoms in a flat-bottom trap allow one to robustly implement a spin model displaying two symmetries: the Sn symmetry that permutes atoms occupying different vibrational levels of the trap and the SU(N) symmetry associated with N nuclear spin states. The symmetries make the model exactly solvable, which, in turn, enables the analytic study of dynamical processes such as spin diffusion in this SU(N) system. We also show how to use this system to generate entangled states that allow for Heisenberg-limited metrology. This highly symmetric spin model should be experimentally realizable even when the vibrational levels are occupied according to a high-temperature thermal or an arbitrary nonthermal distribution.
| S-EPMC6604830 | biostudies-literature
Project description:Biological systems often display modularity, in the sense that they can be decomposed into nearly independent subsystems. Recent studies have suggested that modular structure can spontaneously emerge if goals (environments) change over time, such that each new goal shares the same set of sub-problems with previous goals. Such modularly varying goals can also dramatically speed up evolution, relative to evolution under a constant goal. These studies were based on simulations of model systems, such as logic circuits and RNA structure, which are generally not easy to treat analytically. We present, here, a simple model for evolution under modularly varying goals that can be solved analytically. This model helps to understand some of the fundamental mechanisms that lead to rapid emergence of modular structure under modularly varying goals. In particular, the model suggests a mechanism for the dramatic speedup in evolution observed under such temporally varying goals.
| S-EPMC2661363 | biostudies-literature