Improved quantum circuits for elliptic curve discrete logarithms
- URL: http://arxiv.org/abs/2001.09580v1
- Date: Mon, 27 Jan 2020 04:08:49 GMT
- Title: Improved quantum circuits for elliptic curve discrete logarithms
- Authors: Thomas H\"aner and Samuel Jaques and Michael Naehrig and Martin
Roetteler and Mathias Soeken
- Abstract summary: We present improved quantum circuits for elliptic curve scalar multiplication.
We optimize low-level components such as reversible integer and modular arithmetic.
We provide a full implementation of point addition in the Q# quantum programming language.
- Score: 6.058525641792685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present improved quantum circuits for elliptic curve scalar
multiplication, the most costly component in Shor's algorithm to compute
discrete logarithms in elliptic curve groups. We optimize low-level components
such as reversible integer and modular arithmetic through windowing techniques
and more adaptive placement of uncomputing steps, and improve over previous
quantum circuits for modular inversion by reformulating the binary Euclidean
algorithm. Overall, we obtain an affine Weierstrass point addition circuit that
has lower depth and uses fewer $T$ gates than previous circuits. While previous
work mostly focuses on minimizing the total number of qubits, we present
various trade-offs between different cost metrics including the number of
qubits, circuit depth and $T$-gate count. Finally, we provide a full
implementation of point addition in the Q# quantum programming language that
allows unit tests and automatic quantum resource estimation for all components.
Related papers
- 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) - 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) - Noisy Tensor Ring approximation for computing gradients of Variational
Quantum Eigensolver for Combinatorial Optimization [33.12181620473604]
Variational Quantum algorithms have established their potential to provide computational advantage in the realm of optimization.
These algorithms suffer from classically intractable gradients limiting the scalability.
This work proposes a classical gradient method which utilizes the parameter shift rule but computes the expected values from the circuits using a tensor ring approximation.
arXiv Detail & Related papers (2023-07-08T03:14:28Z) - Approximate Quantum Compiling for Quantum Simulation: A Tensor Network based approach [1.237454174824584]
We introduce AQCtensor, a novel algorithm to produce short-depth quantum circuits from Matrix Product States (MPS)
Our approach is specifically tailored to the preparation of quantum states generated from the time evolution of quantum many-body Hamiltonians.
For simulation problems on 100 qubits, we show that AQCtensor achieves at least an order of magnitude reduction in the depth of the resulting optimized circuit.
arXiv Detail & Related papers (2023-01-20T14:40:29Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Automated Generation of Shuttling Sequences for a Linear Segmented Ion
Trap Quantum Computer [26.47874938214435]
A promising approach for scaling-up trapped-ion quantum computer platforms is by storing multiple trapped-ion qubit sets ('ion crystals') in segmented microchip traps.
Here, we describe an algorithm for fully automated generation of shuttling schedules.
We find that for quantum circuits which contain a fixed structure, advanced assignment algorithms can serve to reduce the shuttling overhead.
arXiv Detail & Related papers (2022-08-09T16:16:43Z) - Reducing the Depth of Quantum FLT-Based Inversion Circuit [0.5735035463793008]
We propose to reduce the depth of the existing quantum Fermat's Little Theorem ( gates)-based inversion circuit for binary finite field.
Our approach can serve as an alternative for a time-efficient implementation.
arXiv Detail & Related papers (2022-04-16T00:20:18Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits.
We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
arXiv Detail & Related papers (2022-01-27T13:16:30Z) - Reducing the Depth of Linear Reversible Quantum Circuits [0.0]
In quantum computing the decoherence time of the qubits determines the computation time available.
We propose a practical formulation of a divide and conquer algorithm that produces quantum circuits that are twice as shallow as those produced by existing algorithms.
Overall, we manage to consistently reduce the total depth of a class of reversible functions, with up to 92% savings in an ancilla-free case and up to 99% when ancillary qubits are available.
arXiv Detail & Related papers (2022-01-17T12:36:32Z) - Halving the cost of quantum multiplexed rotations [0.0]
We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls.
Our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations.
arXiv Detail & Related papers (2021-10-26T06:49:44Z) - 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.