Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum resource estimates for computing elliptic curve discrete logarithms
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give precise quantum resource estimates for Shors algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2lceillog_2(n)rceil+10$ qubits using a quantum circuit of at most $448 n^3 log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shors algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shors factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.
rate research
Read More
We present improved quantum circuits for elliptic curve scalar multiplication, the most costly component in Shors 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.
We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shors algorithms for period finding and discrete log as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $k ge 2$ generators in a black-box abelian semigroup of order $N$ requires $tilde Theta(N^{frac{1}{2}-frac{1}{2k}})$ quantum queries.
We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on LUT networks (lookup-table networks), which play a key role in conventional logic synthesis. Establishing a connection between LUTs in a LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based Hierarchical Reversible Logic Synthesis (LHRS). Input to LHRS is a classical logic network; output is a quantum network (realized in terms of Clifford+$T$ gates). The framework offers to trade-off the number of qubits for the number of quantum gates. In a first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+$T$ gates, while aiming at optimally using available resources. We demonstrate the effectiveness of our method in automatically synthesizing IEEE compliant floating point networks up to double precision. As many quantum algorithms target scientific simulation applications, they can make rich use of floating point arithmetic components. But due to the lack of quantum circuit descriptions for those components, it can be difficult to find a realistic cost estimation for the algorithms. Our synthesized benchmarks provide cost estimates that allow quantum algorithm designers to provide the first complete cost estimates for a host of quantum algorithms. Thus, the benchmarks and, more generally, the LHRS framework are an essential step towards the goal of understanding which quantum algorithms will be practical in the first generations of quantum computers.
We present a number of quantum computing patterns that build on top of fundamental algorithms, that can be applied to solving concrete, NP-hard problems. In particular, we introduce the concept of a quantum dictionary as a summation of multiple patterns and algorithms, and show how it can be applied in the context of Quadratic Unconstrained Binary Optimization (QUBO) problems. We start by presenting a visual approach to quantum computing, which avoids a heavy-reliance on quantum mechanics, linear algebra, or complex mathematical notation, and favors geometrical intuition and computing paradigms. We also provide insights on the fundamental quantum computing algorithms (Fourier Transforms, Phase Estimation, Grover, Quantum Counting, and Amplitude Estimation).
The ability to simulate a fermionic system on a quantum computer is expected to revolutionize chemical engineering, materials design, nuclear physics, to name a few. Thus, optimizing the simulation circuits is of significance in harnessing the power of quantum computers. Here, we address this problem in two aspects. In the fault-tolerant regime, we optimize the $rzgate$ and $tgate$ gate counts along with the ancilla qubit counts required, assuming the use of a product-formula algorithm for implementation. We obtain a savings ratio of two in the gate counts and a savings ratio of eleven in the number of ancilla qubits required over the state of the art. In the pre-fault tolerant regime, we optimize the two-qubit gate counts, assuming the use of the variational quantum eigensolver (VQE) approach. Specific to the latter, we present a framework that enables bootstrapping the VQE progression towards the convergence of the ground-state energy of the fermionic system. This framework, based on perturbation theory, is capable of improving the energy estimate at each cycle of the VQE progression, by about a factor of three closer to the known ground-state energy compared to the standard VQE approach in the test-bed, classically-accessible system of the water molecule. The improved energy estimate in turn results in a commensurate level of savings of quantum resources, such as the number of qubits and quantum gates, required to be within a pre-specified tolerance from the known ground-state energy. We also explore a suite of generalized transformations of fermion to qubit operators and show that resource-requirement savings of up to more than $20%$, in small instances, is possible.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
