Accelerated Quantum Amplitude Estimation without QFT
- URL: http://arxiv.org/abs/2407.16795v1
- Date: Tue, 23 Jul 2024 18:49:11 GMT
- Title: Accelerated Quantum Amplitude Estimation without QFT
- Authors: Alet Roux, Tomasz Zastawniak,
- Abstract summary: We put forward a Quantum Amplitude Estimation algorithm delivering superior performance (lower quantum computational complexity and faster classical computation parts) compared to the approaches available to-date.
The correctness of the algorithm and the $O(frac1varepsilon)$ bound on quantum computational complexity are supported by precise proofs.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We put forward a Quantum Amplitude Estimation algorithm delivering superior performance (lower quantum computational complexity and faster classical computation parts) compared to the approaches available to-date. The algorithm does not relay on the Quantum Fourier Transform and its quantum computational complexity is of order $O(\frac{1}{\varepsilon})$ in terms of the target accuracy $\varepsilon>0$. The $O(\frac{1}{\varepsilon})$ bound on quantum computational complexity is also superior compared to those in the earlier approaches due to smaller constants. Moreover, a much tighter bound is obtained by means of computer-assisted estimates for the expected value of quantum computational complexity. The correctness of the algorithm and the $O(\frac{1}{\varepsilon})$ bound on quantum computational complexity are supported by precise proofs.
Related papers
- Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures [41.39072840772559]
Route-Forcing is a quantum circuit mapping algorithm that shows an average speedup of $3.7times$.
We present a quantum circuit mapping algorithm that shows an average speedup of $3.7times$ compared to the state-of-the-art scalable techniques.
arXiv Detail & Related papers (2024-07-24T14:21:41Z) - A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
We introduce a novel quantum XZ24 algorithm, designed for efficiently computing the eigen-energy spectra of any quantum systems.
Compared to existing quantum methods, the new algorithm stands out for its remarkably low measurement cost.
We anticipate that the new algorithm will drive significant progress in quantum system simulation and offer promising applications in quantum computing and quantum information processing.
arXiv Detail & Related papers (2024-06-01T04:31:43Z) - Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit.
Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets.
Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
arXiv Detail & Related papers (2024-02-22T09:20:54Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Quantum Phase Estimation by Compressed Sensing [0.0]
We present a new Heisenberg-limited quantum phase estimation algorithm for early quantum computers based on compressed sensing.
Our algorithm is able to recover the frequency with a total runtime $mathcalO(epsilon-1textpolylog(epsilon-1))$, where $epsilon$ is the accuracy.
We also consider the more general quantum eigenvalue estimation problem (QEEP) and show numerically that the off-grid compressed sensing can be a strong candidate for solving the QEEP.
arXiv Detail & Related papers (2023-06-12T10:21:59Z) - Quantum Distance Calculation for $\epsilon$-Graph Construction [0.0]
We investigate the potential for quantum advantage in the case of quantum distance calculation for computing $epsilon$-graphs.
We show that, relying on existing quantum multi-state SWAP test based algorithms, the query complexity for correctly identifying two points are not $epsilon$-neighbours is at least O(n3 / ln n)
arXiv Detail & Related papers (2023-06-07T09:43:28Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP)
We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
arXiv Detail & Related papers (2021-09-23T07:46:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.