Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal algorithms for linear algebra by quantum inspiration
137
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Recent results by Harrow et. al. and by Ta-Shma, suggest that quantum computers may have an exponential advantage in solving a wealth of linear algebraic problems, over classical algorithms. Building on the quantum intuition of these results, we step back into the classical domain, and explore its usefulness in designing classical algorithms. We achieve an algorithm for solving the major linear-algebraic problems in time $O(n^{omega+ u})$ for any $ u>0$, where $omega$ is the optimal matrix-product constant. Thus our algorithm is optimal w.r.t. matrix multiplication, and comparable to the state-of-the-art algorithm for these problems due to Demmel et. al. Being derived from quantum intuition, our proposed algorithm is completely disjoint from all previous classical algorithms, and builds on a combination of low-discrepancy sequences and perturbation analysis. As such, we hope it motivates further exploration of quantum techniques in this respect, hopefully leading to improvements in our understanding of space complexity and numerical stability of these problems.
rate research
Read More
Quantum algorithms have been developed for efficiently solving linear algebra tasks. However, they generally require deep circuits and hence universal fault-tolerant quantum computers. In this work, we propose variational algorithms for linear algebra tasks that are compatible with noisy intermediate-scale quantum devices. We show that the solutions of linear systems of equations and matrix-vector multiplications can be translated as the ground states of the constructed Hamiltonians. Based on the variational quantum algorithms, we introduce Hamiltonian morphing together with an adaptive ansatz for efficiently finding the ground state, and show the solution verification. Our algorithms are especially suitable for linear algebra problems with sparse matrices, and have wide applications in machine learning and optimisation problems. The algorithm for matrix multiplications can be also used for Hamiltonian simulation and open system simulation. We evaluate the cost and effectiveness of our algorithm through numerical simulations for solving linear systems of equations. We implement the algorithm on the IBM quantum cloud device with a high solution fidelity of 99.95%.
Quantum adiabatic algorithm is of vital importance in quantum computation field. It offers us an alternative approach to manipulate the system instead of quantum gate model. Recently, an interesting work arXiv:1805.10549 indicated that we can solve linear equation system via algorithm inspired by adiabatic quantum computing. Here we demonstrate the algorithm and realize the solution of 8-dimensional linear equations $Atextbf{x}=textbf{b}$ in a 4-qubit nuclear magnetic resonance system. The result is by far the solution of maximum-dimensional linear equation with a limited number of qubits in experiments, which includes some ingenious simplifications. Our experiment provides the new possibility of solving so many practical problems related to linear equations systems and has the potential applications in designing the future quantum algorithms.
We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically Theta((n/p)^{2/3}) p-parallel queries for element distinctness and Theta((n/p)^{k/(k+1)} for k-sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel complexity are polynomially related for all total functions f when p is small compared to fs block sensitivity.
Surface codes are among the best candidates to ensure the fault-tolerance of a quantum computer. In order to avoid the accumulation of errors during a computation, it is crucial to have at our disposal a fast decoding algorithm to quickly identify and correct errors as soon as they occur. We propose a linear-time maximum likelihood decoder for surface codes over the quantum erasure channel. This decoding algorithm for dealing with qubit loss is optimal both in terms of performance and speed.
We use our Clifford algebra technique, that is nilpotents and projectors which are binomials of the Clifford algebra objects $gamma^a$ with the property ${gamma^a,gamma^b}_+ = 2 eta^{ab}$, for representing quantum gates and quantum algorithms needed in quantum computers in an elegant way. We identify $n$-qubits with spinor representations of the group SO(1,3) for a system of $n$ spinors. Representations are expressed in terms of products of projectors and nilpotents. An algorithm for extracting a particular information out of a general superposition of $2^n$ qubit states is presented. It reproduces for a particular choice of the initial state the Grovers algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
