Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThermodynamic Analysis of Classical and Quantum Search Algorithms
55
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyze the performance of classical and quantum search algorithms from a thermodynamic perspective, focusing on resources such as time, energy, and memory size. We consider two examples that are relevant to post-quantum cryptography: Grovers search algorithm, and the quantum algorithm for collision-finding. Using Bennetts Brownian model of low-power reversible computation, we show classical algorithms that have the same asymptotic energy consumption as these quantum algorithms. Thus, the quantum advantage in query complexity does not imply a reduction in these thermodynamic resource costs. In addition, we present realistic estimates of the resource costs of quantum and classical search, for near-future computing technologies. We find that, if memory is cheap, classical exhaustive search can be surprisingly competitive with Grovers algorithm.
rate research
Read More
We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space. The classical algorithms that we present are related to, but slightly different from those presented recently in Ref. 1. In particular, we have an improved threshold for recovery and the algorithms we present work for both even and odd order tensors. These results suggest that large-scale inference problems are a promising future application for quantum computers.
The recursion equation analysis of Grovers quantum search algorithm presented by Biham et al. [PRA 60, 2742 (1999)] is generalized. It is applied to the large class of Grovers type algorithms in which the Hadamard transform is replaced by any other unitary transformation and the phase inversion is replaced by a rotation by an arbitrary angle. The time evolution of the amplitudes of the marked and unmarked states, for any initial complex amplitude distribution is expressed using first order linear difference equations. These equations are solved exactly. The solution provides the number of iterations T after which the probability of finding a marked state upon measurement is the highest, as well as the value of this probability, P_max. Both T and P_max are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments.
Quantum computers can exploit a Hilbert space whose dimension increases exponentially with the number of qubits. In experiment, quantum supremacy has recently been achieved by the Google team by using a noisy intermediate-scale quantum (NISQ) device with over 50 qubits. However, the question of what can be implemented on NISQ devices is still not fully explored, and discovering useful tasks for such devices is a topic of considerable interest. Hybrid quantum-classical algorithms are regarded as well-suited for execution on NISQ devices by combining quantum computers with classical computers, and are expected to be the first useful applications for quantum computing. Meanwhile, mitigation of errors on quantum processors is also crucial to obtain reliable results. In this article, we review the basic results for hybrid quantum-classical algorithms and quantum error mitigation techniques. Since quantum computing with NISQ devices is an actively developing field, we expect this review to be a useful basis for future studies.
We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of local classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of global classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.
We give efficient quantum algorithms to estimate the partition function of (i) the six vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi 2D square lattice, and (iv) the Z_2 lattice gauge theory on a three-dimensional square lattice. Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation. The results are proven for a complex parameter regime of the models. The proofs are based on a mapping relating partition functions to quantum circuits introduced in [Van den Nest et al., Phys. Rev. A 80, 052334 (2009)] and extended here.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
