Fast quantum integer multiplication with zero ancillas
- URL: http://arxiv.org/abs/2403.18006v3
- Date: Fri, 14 Jun 2024 20:29:46 GMT
- Title: Fast quantum integer multiplication with zero ancillas
- Authors: Gregory D. Kahanamoku-Meyer, Norman Y. Yao,
- Abstract summary: We introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits.
The only qubits involved are the input and output registers themselves.
Our algorithm has the potential to outperform previous problem sizes relevant in practice.
- Score: 0.5755004576310334
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of $\mathcal{O}(n^{1+\epsilon})$ for any $\epsilon > 0$; with practical choices of parameters, we expect scalings as low as $\mathcal{O}(n^{1.3})$. Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with $\mathcal{O}(n^{2+\epsilon})$ gates and only $2n + \mathcal{O}(\log n)$ qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is $\mathcal{O}(n^{1.5+\epsilon})$. Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.
Related papers
- Quantum hashing algorithm implementation [0.0]
We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers.
We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one.
arXiv Detail & Related papers (2024-07-14T09:41:16Z) - Lower $T$-count with faster algorithms [3.129187821625805]
We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times.
We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits.
We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
arXiv Detail & Related papers (2024-07-11T17:31:20Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods.
We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM)
The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
arXiv Detail & Related papers (2024-01-20T15:32:01Z) - An Efficient Quantum Factoring Algorithm [0.27195102129094995]
We show that $n$bit integers can be factorized by independently running a quantum circuit with $tildeO(n3/2)$.
The correctness of the algorithm relies on a number-theoretic assumption reminiscent of those used in subexponential classical factorization algorithms.
arXiv Detail & Related papers (2023-08-12T13:57:38Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Beyond Ans\"atze: Learning Quantum Circuits as Unitary Operators [30.5744362478158]
We run gradient-based optimization in the Lie algebra $mathfrak u(2N)$.
We argue that $U(2N)$ is not only more general than the search space induced by ansatz, but in ways easier to work with on classical computers.
arXiv Detail & Related papers (2022-03-01T16:40:21Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - CNOT-count optimized quantum circuit of the Shor's algorithm [8.88308897530269]
We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization.
According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer.
arXiv Detail & Related papers (2021-12-21T16:56:22Z) - Low-depth Quantum State Preparation [3.540171881768714]
A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=lceil logNrceil$-qubit state.
Here we investigate this space-time tradeoff in quantum state preparation with classical data.
We propose quantum algorithms with $mathcal O(n2)$ circuit depth to encode any $N$ complex numbers.
arXiv Detail & Related papers (2021-02-15T13:11:43Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.