Optimal Coherent Quantum Phase Estimation via Tapering
- URL: http://arxiv.org/abs/2403.18927v1
- Date: Wed, 27 Mar 2024 18:17:23 GMT
- Title: Optimal Coherent Quantum Phase Estimation via Tapering
- Authors: Dhrumil Patel, Shi Jie Samuel Tan, Yigit Subasi, Andrew T. Sornborger,
- Abstract summary: We study the coherent version of the phase estimation problem.
The goal is to estimate the phases of $U$ in superposition.
We propose an improved version of the well-known standard quantum phase estimation algorithm.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum phase estimation is one of the fundamental primitives that underpins many quantum algorithms, including quantum amplitude estimation, the HHL algorithm for solving linear systems of equations, and quantum principal component analysis. Due to its significance as a subroutine, in this work, we study the coherent version of the phase estimation problem, where given an arbitrary input state and black-box access to unitaries $U$ and controlled-$U$, the goal is to estimate the phases of $U$ in superposition. Unlike most existing phase estimation algorithms, which employ intermediary measurements steps that inevitably destroy coherence, only a couple of algorithms, including the well-known standard quantum phase estimation algorithm, consider this coherent setting. In this work, we propose an improved version of this standard algorithm that utilizes tapering/window functions. Our algorithm, which we call tapered quantum phase estimation algorithm, achieves the optimal query complexity (total number of calls to $U$ and controlled-$U$) without requiring the use of a computationally expensive quantum sorting network for median computation, which the standard algorithm uses to boost the success probability arbitrarily close to one. We also show that the tapering functions that we use are optimal by formulating optimization problems with different optimization criteria. Beyond the asymptotic regime, we also provide non-asymptotic query complexity of our algorithm, as it is crucial for practical implementation. Finally, we also propose an efficient algorithm that prepares the quantum state corresponding to the optimal tapering function.
Related papers
- A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
We present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error.
In the presence of noise, our algorithm produces errors that approach the theoretical lower bound.
arXiv Detail & Related papers (2023-03-02T19:00:01Z) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
We propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy.
We analytically show that a first-order phase transition is successfully avoided for a fully connected ferro Potts model if the overlap between a ground state and a candidate solution exceeds a threshold.
arXiv Detail & Related papers (2022-11-08T02:12:49Z) - Iteration Complexity of Variational Quantum Algorithms [5.684122393859336]
We argue that noise makes evaluations of the objective function via quantum circuits biased.
We derive the missing guarantees and find that the rate of convergence is unaffected.
arXiv Detail & Related papers (2022-09-21T19:18:41Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Reducing the cost of energy estimation in the variational quantum
eigensolver algorithm with robust amplitude estimation [50.591267188664666]
Quantum chemistry and materials is one of the most promising applications of quantum computing.
Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
arXiv Detail & Related papers (2022-03-14T16:51:36Z) - Stochastic optimization algorithms for quantum applications [0.0]
We review the use of first-order, second-order, and quantum natural gradient optimization methods, and propose new algorithms defined in the field of complex numbers.
The performance of all methods is evaluated by means of their application to variational quantum eigensolver, quantum control of quantum states, and quantum state estimation.
arXiv Detail & Related papers (2022-03-11T16:17:05Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace.
One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz.
We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
arXiv Detail & Related papers (2021-05-14T11:31:14Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
Variational quantum algorithms are believed to be promising for solving computationally hard problems.
In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances.
Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
arXiv Detail & Related papers (2020-05-11T17:20:51Z)
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.