Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExperimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
406
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $Ax = b$, we show that there is a classical algorithm that outputs a data structure for $x$ allowing sampling and querying to the entries, where $x$ is such that $|x - A^{-1}b|leq epsilon |A^{-1}b|$. This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $widetilde{O}(kappa_F^6 kappa^2/epsilon^2 )$, where $kappa_F = |A|_F|A^{-1}|$ and $kappa = |A||A^{-1}|$. This improves the previous best algorithm [Gily{e}n, Song and Tang, arXiv:2009.07268] of complexity $widetilde{O}(kappa_F^6 kappa^6/epsilon^4)$. Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when $A$ is row sparse, this method already returns an approximate solution $x$ in time $widetilde{O}(kappa_F^2)$, while the best quantum algorithm known returns $ket{x}$ in time $widetilde{O}(kappa_F)$ when $A$ is stored in the QRAM data structure. As a result, assuming access to QRAM and if $A$ is row sparse, the speedup based on current quantum algorithms is quadratic.
Quantum computers have the potential of solving certain problems exponentially faster than classical computers. Recently, Harrow, Hassidim and Lloyd proposed a quantum algorithm for solving linear systems of equations: given an $Ntimes{N}$ matrix $A$ and a vector $vec b$, find the vector $vec x$ that satisfies $Avec x = vec b$. It has been shown that using the algorithm one could obtain the solution encoded in a quantum state $|x$ using $O(log{N})$ quantum operations, while classical algorithms require at least O(N) steps. If one is not interested in the solution $vec{x}$ itself but certain statistical feature of the solution ${x}|M|x$ ($M$ is some quantum mechanical operator), the quantum algorithm will be able to achieve exponential speedup over the best classical algorithm as $N$ grows. Here we report a proof-of-concept experimental demonstration of the quantum algorithm using a 4-qubit nuclear magnetic resonance (NMR) quantum information processor. For all the three sets of experiments with different choices of $vec b$, we obtain the solutions with over 96% fidelity. This experiment is a first implementation of the algorithm. Because solving linear systems is a common problem in nearly all fields of science and engineering, we will also discuss the implication of our results on the potential of using quantum computers for solving practical linear systems.
Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2*2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.
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.
In counterfactual QKD information is transfered, in a secure way, between Alice and Bob even when no particle carrying the information is in fact transmitted between them. In this letter we fully implement the scheme for counterfactual QKD proposed in [T. Noh, PRL textbf{103}, 230501 (2009)], demonstrating for the first time that information can be transmitted between two parties without the transmission of a carrier.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
