Quantum hyperparallel algorithm for matrix multiplication.
Ontology highlight
ABSTRACT:
SUBMITTER: Zhang XD
PROVIDER: S-EPMC4850379 | biostudies-other | 2016 Apr
REPOSITORIES: biostudies-other
Similar Datasets
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:Cohn and Umans proposed a framework for developing fast matrix multiplication algorithms based on the embedding computation in certain groups algebras [9]. In subsequent work with Kleinberg and Szegedy, they connected this to the search for combinatorial objects called strong uniquely solvable puzzles (strong USPs) [8]. We begin a systematic computer-aided search for these objects. We develop and implement algorithms based on reductions to
| S-EPMC7326541 | biostudies-literature
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:As a fundamental primitive, Secure Multiparty Summation and Multiplication can be used to build complex secure protocols for other multiparty computations, specially, numerical computations. However, there is still lack of systematical and efficient quantum methods to compute Secure Multiparty Summation and Multiplication. In this paper, we present a novel and efficient quantum approach to securely compute the summation and multiplication of multiparty private inputs, respectively. Compared to classical solutions, our proposed approach can ensure the unconditional security and the perfect privacy protection based on the physical principle of quantum mechanics.
| S-EPMC4726197 | biostudies-other
Project description:The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum algorithm which fully generalizes the classical Metropolis algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.
| S-EPMC3271878 | biostudies-other
Project description:Carrier multiplication (CM) holds great promise to break the Shockley-Queisser limit of single junction photovoltaic cells. Despite compelling spectroscopic evidence of strong CM effects in halide perovskites, studies in actual perovskite solar cells (PSCs) are lacking. Herein, we reconcile this knowledge gap using the testbed Cs0.05FA0.5MA0.45Pb0.5Sn0.5I3 system exhibiting efficient CM with a low threshold of 2Eg (~500 nm) and high efficiency of 99.4 ± 0.4%. Robust CM enables an unbiased internal quantum efficiency exceeding 110% and reaching as high as 160% in the best devices. Importantly, our findings inject fresh insights into the complex interplay of various factors (optical and parasitic absorption losses, charge recombination and extraction losses, etc.) undermining CM contributions to the overall performance. Surprisingly, CM effects may already exist in mixed Pb-Sn PSCs but are repressed by its present architecture. A comprehensive redesign of the existing device configuration is needed to leverage CM effects for next-generation PSCs.
| S-EPMC10562407 | biostudies-literature
Project description:Designing quantum algorithms for simulating quantum systems has seen enormous progress, yet few studies have been done to develop quantum algorithms for open quantum dynamics despite its importance in modeling the system-environment interaction found in most realistic physical models. In this work we propose and demonstrate a general quantum algorithm to evolve open quantum dynamics on quantum computing devices. The Kraus operators governing the time evolution can be converted into unitary matrices with minimal dilation guaranteed by the Sz.-Nagy theorem. This allows the evolution of the initial state through unitary quantum gates, while using significantly less resource than required by the conventional Stinespring dilation. We demonstrate the algorithm on an amplitude damping channel using the IBM Qiskit quantum simulator and the IBM Q 5 Tenerife quantum device. The proposed algorithm does not require particular models of dynamics or decomposition of the quantum channel, and thus can be easily generalized to other open quantum dynamical models.
| S-EPMC7039952 | biostudies-literature
Project description:One process limiting the performance of solar cells is rapid cooling (thermalization) of hot carriers generated by higher-energy solar photons. In principle, the thermalization losses can be reduced by converting the kinetic energy of energetic carriers into additional electron-hole pairs via carrier multiplication (CM). While being inefficient in bulk semiconductors this process is enhanced in quantum dots, although not sufficiently high to considerably boost the power output of practical devices. Here we demonstrate that thick-shell PbSe/CdSe nanostructures can show almost a fourfold increase in the CM yield over conventional PbSe quantum dots, accompanied by a considerable reduction of the CM threshold. These structures enhance a valence-band CM channel due to effective capture of energetic holes into long-lived shell-localized states. The attainment of the regime of slowed cooling responsible for CM enhancement is indicated by the development of shell-related emission in the visible observed simultaneously with infrared emission from the core.
| S-EPMC4083434 | biostudies-other
Project description:Carrier multiplication, the generation of multiple electron-hole pairs by a single photon, is of great interest for solar cells as it may enhance their photocurrent. This process has been shown to occur efficiently in colloidal quantum dots, however, harvesting of the generated multiple charges has proved difficult. Here we show that by tuning the charge-carrier mobility in quantum-dot films, carrier multiplication can be optimized and may show an efficiency as high as in colloidal dispersion. Our results are explained quantitatively by the competition between dissociation of multiple electron-hole pairs and Auger recombination. Above a mobility of ~1 cm(2) V(-1) s(-1), all charges escape Auger recombination and are quantitatively converted to free charges, offering the prospect of cheap quantum-dot solar cells with efficiencies in excess of the Shockley-Queisser limit. In addition, we show that the threshold energy for carrier multiplication is reduced to twice the band gap of the quantum dots.
| S-EPMC3759061 | biostudies-literature
Project description:Quantum information processing enhances human's power to simulate nature in quantum level and solve complex problem efficiently. During the process, a series of operators is performed to evolve the system or undertake a computing task. In recent year, research interest in non-Hermitian quantum systems, dissipative-quantum systems and new quantum algorithms has greatly increased, which nonunitary operators take an important role in. In this work, we utilize the linear combination of unitaries technique for nonunitary dynamics on a single qubit to give explicit decompositions of the necessary unitaries, and simulate arbitrary time-dependent single-qubit nonunitary operator F(t) using duality quantum algorithm. We find that the successful probability is not only decided by F(t) and the initial state, but also is inversely proportional to the dimensions of the used ancillary Hilbert subspace. In a general case, the simulation can be achieved in both eight- and six-dimensional Hilbert spaces. In phase matching conditions, F(t) can be simulated by only two qubits. We illustrate our method by simulating typical non-Hermitian systems and single-qubit measurements. Our method can be extended to high-dimensional case, such as Abrams-Lloyd's two-qubit gate. By discussing the practicability, we expect applications and experimental implementations in the near future.
| S-EPMC7889913 | biostudies-literature