Quantum Phase Estimation Algorithm for Finding Polynomial Roots
arXiv:1510.04452 · doi:10.1515/phys-2019-0087
Abstract
Quantum algorithm is an algorithm for solving mathematical problems using quantum systems encoded as information, which is found to outperform classical algorithms in some specific cases. The objective of this study is to develop a quantum algorithm for finding the roots of nth degree polynomials where n is any positive integer. In classical algorithm, the resources required for solving this problem increase drastically when n increases and it would be impossible to practically solve the problem when n is large. It was found that any polynomial can be rearranged into a corresponding companion matrix, whose eigenvalues are roots of the polynomial. This leads to a possibility to perform a quantum algorithm where the number of computational resources increase as a polynomial of n. In this study, we construct a quantum circuit representing the companion matrix and use eigenvalue estimation technique to find roots of polynomial.
References in corpus (17)
- Elementary gates for quantum computation
- Simulated Quantum Computation of Molecular Energies
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Semiclassical Fourier Transform for Quantum Computation
- Experimental quantum-enhanced estimation of a lossy phase shift
- A Universal Two--Bit Gate for Quantum Computation
- Quantum simulation of the wavefunction to probe frustrated Heisenberg spin systems
- Solving systems of linear equations on a quantum computer
- Simulating quantum statistics with entangled photons: a continuous transition from bosons to fermions
- Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
- Liquid state NMR simulations of quantum many-body problems
- Calculating Unknown Eigenvalues with a Quantum Algorithm
- Suppression laws for multi-particle interference in Sylvester interferometers
- Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices
- Universal Programmable Quantum Circuit Schemes to Emulate an Operator
- A Universal Quantum Circuit Scheme For Finding Complex Eigenvalues
- Correlation functions and momentum distribution of one-dimensional hard-core anyons in optical lattices