Quantum resource estimates for computing binary elliptic curve discrete logarithms

• URL: http://arxiv.org/abs/2503.02984v1
• Date: Tue, 04 Mar 2025 20:18:50 GMT
• Title: Quantum resource estimates for computing binary elliptic curve discrete logarithms
• Authors: Michael Garn, Angus Kan,
• Abstract summary: We adopt a windowed approach to design our circuit implementation of Shor's algorithm.<n>We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes.<n>We estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We perform logical and physical resource estimation for computing binary elliptic curve discrete logarithms using Shor's algorithm on fault-tolerant quantum computers. We adopt a windowed approach to design our circuit implementation of the algorithm, which comprises repeated applications of elliptic curve point addition operations and table look-ups. Unlike previous work, the point addition operation is implemented exactly, including all exceptional cases. We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes. Furthermore, we estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers with a baseline architecture, where logical qubits have nearest-neighbor connectivity, and on a surface-code photonic fusion-based quantum computer with an active-volume architecture, which enjoys a logarithmic number of non-local connections between logical qubits. At 10$\%$ threshold and compared to a baseline device with a $1\mu s$ code cycle, our algorithm runs $\gtrsim$ 2-20 times faster, depending on the operating regime of the hardware and over all considered field sizes, on a photonic active-volume device.

Related papers

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Quantum Optical Approach to the $K$ Nearest Neighbour Algorithm [1.904851064759821]
  We construct a hybrid quantum-classical approach for the $K$-Nearest Neighbour algorithm. The information is embedded in a phase-distributed multimode coherent state with the assistance of a single photon. We provide the quantum optical architecture corresponding to our algorithm.
  arXiv  Detail & Related papers  (2024-04-18T09:33:31Z)
• Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections [0.0]
  We introduce an architecture using non-2D-local connections in which the cost does not scale with the number of qubits. We show that, using the same number of logical qubits, a 2048-bit factoring algorithm can be executed 44 times faster than on a general-purpose architecture.
  arXiv  Detail & Related papers  (2022-11-28T15:51:58Z)
• Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
  We introduce a quantum-control-inspired method for the characterization of variational quantum circuits using the rank of the dynamical Lie algebra. A promising connection is found between the Lie rank, the accuracy of calculated energies, and the requisite depth to attain target states via a given circuit architecture.
  arXiv  Detail & Related papers  (2022-09-28T20:24:53Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Approximate encoding of quantum states using shallow circuits [0.0]
  A common requirement of quantum simulations and algorithms is the preparation of complex states through sequences of 2-qubit gates. Here, we aim at creating an approximate encoding of the target state using a limited number of gates. Our work offers a universal method to prepare target states using local gates and represents a significant improvement over known strategies.
  arXiv  Detail & Related papers  (2022-06-30T18:00:04Z)
• Logical blocks for fault-tolerant topological quantum computation [55.41644538483948]
  We present a framework for universal fault-tolerant logic motivated by the need for platform-independent logical gate definitions. We explore novel schemes for universal logic that improve resource overheads. Motivated by the favorable logical error rates for boundaryless computation, we introduce a novel computational scheme.
  arXiv  Detail & Related papers  (2021-12-22T19:00:03Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Leveraging state sparsity for more efficient quantum simulations [1.52292571922932]
  We introduce a new simulation method that exploits this sparsity to reduce memory usage and simulation runtime. Our prototype implementation includes optimizations such as gate (re)scheduling, which amortizes data structure accesses and reduces memory usage. Our simulator successfully runs a factoring instance of a 20-bit number using 102 qubits, and elliptic curve discrete logarithm over a 10-bit curve with 110 qubits.
  arXiv  Detail & Related papers  (2021-05-04T14:42:32Z)
• 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)
• 2D Qubit Placement of Quantum Circuits using LONGPATH [1.6631602844999722]
  Two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. Our approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
  arXiv  Detail & Related papers  (2020-07-14T04:09:52Z)

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.