Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn efficient quantum algorithm for spectral estimation
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
An algorithm that initializes a quantum register to a state with a specified energy range is given, corresponding to a quantum implementation of the celebrated Feit-Fleck method. This is performed by introducing a nondeterministic quantum implementation of a standard spectral filtering procedure combined with an apodization technique, allowing for accurate state initialization. It is shown that the implementation requires only two ancilla qubits. A lower bound for the total probability of success of this algorithm is derived, showing that this scheme can be realized using a finite, relatively low number of trials. Assuming the time evolution can be performed efficiently and using a trial state polynomially close to the desired states, it is demonstrated that the number of operations required scales polynomially with the number of qubits. Tradeoffs between accuracy and performance are demonstrated in a simple example: the harmonic oscillator. This algorithm would be useful for the initialization phase of the simulation of quantum systems on digital quantum computers.
For two unknown quantum states $rho$ and $sigma$ in an $N$-dimensional Hilbert space, computing their fidelity $F(rho,sigma)$ is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this Letter, we propose a quantum algorithm that solves this problem in $text{poly}(log (N), r)$ time, where $r$ is the lower rank of $rho$ and $sigma$. This algorithm exhibits an exponential improvement over the best-known algorithm (based on quantum state tomography) in $text{poly}(N, r)$ time.
Privacy amplification (PA) is an essential part in a quantum key distribution (QKD) system, distilling a highly secure key from a partially secure string by public negotiation between two parties. The optimization objectives of privacy amplification for QKD are large block size, high throughput and low cost. For the global optimization of these objectives, a novel privacy amplification algorithm is proposed in this paper by combining multilinear-modular-hashing and modular arithmetic hashing. This paper proves the security of this hybrid hashing PA algorithm within the framework of both information theory and composition security theory. A scheme based on this algorithm is implemented and evaluated on a CPU platform. The results on a typical CV-QKD system indicate that the throughput of this scheme ([email protected]*10^8 input block size) is twice higher than the best existing scheme (140Mbps@1*10^8 input block size). Moreover, This scheme is implemented on a mobile CPU platform instead of a desktop CPU or a server CPU, which means that this algorithm has a better performance with a much lower cost and power consumption.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grovers search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grovers search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grovers search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor 16], in which the basis entries satisfy a certain co-primality condition. Using a smooth analysis of lattices by SysNF lattices we design a quantum algorithm that can efficiently solve the following variant of the bounded-distance-decoding problem: given a lattice L, a vector v, and numbers b = {lambda}_1(L)/n^{17}, a = {lambda}_1(L)/n^{13} decide if vs distance from L is in the range [a/2, a] or at most b, where {lambda}_1(L) is the length of Ls shortest non-zero vector. Improving these parameters to a = b = {lambda}_1(L)/sqrt{n} would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
