Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Improved Quantum Scheduling Algorithm
48
0
0.0
(
0
)
Authors
Lov K. Grover
Ask ChatGPT about the research
No Arabic abstract
The scheduling problem consists of finding a common 1 in two remotely located N bit strings. Denote the number of 1s in the string with the fewer 1s by epsilon*N. Classically, it needs at least O(epsilon*N) bits of communication to find the common 1 (ignoring logarithmic factors). The best known quantum algorithm would require O(sqrt(N)) qubits of communication. This paper gives a modified quantum algorithm to find the common 1 with only O(sqrt(epsilon*N)) qubits of communication.
rate research
Read More
Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a quantum algorithm to implement principal component analysis on quantum computer was obtained by computing the Hamiltonian simulation of unknown density operators. The complexity is $O((log d)t^2/epsilon)$, where $d$ is the dimension, $t$ is the evolution time and $epsilon$ is the precision. We improve this result into $O((log d)t^{1+frac{1}{k}}/epsilon^{frac{1}{k}})$ for arbitrary constant integer $kgeq 1$. As a result, we show that the Hamiltonian simulation of low-rank dense Hermitian matrices can be implemented in the same time.
We develop an efficient quantum implementation of an important signal processing algorithm for line spectral estimation: the matrix pencil method, which determines the frequencies and damping factors of signals consisting of finite sums of exponentially damped sinusoids. Our algorithm provides a quantum speedup in a natural regime where the sampling rate is much higher than the number of sinusoid components. Along the way, we develop techniques that are expected to be useful for other quantum algorithms as well - consecutive phase estimations to efficiently make products of asymmetric low rank matrices classically accessible and an alternative method to efficiently exponentiate non-Hermitian matrices. Our algorithm features an efficient quantum-classical division of labor: The time-critical steps are implemented in quantum superposition, while an interjacent step, requiring only exponentially few parameters, can operate classically. We show that frequencies and damping factors can be obtained in time logarithmic in the number of sampling points, exponentially faster than known classical algorithms.
We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.
We report the realization of a nuclear magnetic resonance computer with three quantum bits that simulates an adiabatic quantum optimization algorithm. Adiabatic quantum algorithms offer new insight into how quantum resources can be used to solve hard problems. This experiment uses a particularly well suited three quantum bit molecule and was made possible by introducing a technique that encodes general instances of the given optimization problem into an easily applicable Hamiltonian. Our results indicate an optimal run time of the adiabatic algorithm that agrees well with the prediction of a simple decoherence model.
Present-day, noisy, small or intermediate-scale quantum processors---although far from fault-tolerant---support the execution of heuristic quantum algorithms, which might enable a quantum advantage, for example, when applied to combinatorial optimization problems. On small-scale quantum processors, validations of such algorithms serve as important technology demonstrators. We implement the quantum approximate optimization algorithm (QAOA) on our hardware platform, consisting of two superconducting transmon qubits and one parametrically modulated coupler. We solve small instances of the NP-complete exact-cover problem, with 96.6% success probability, by iterating the algorithm up to level two.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
