Integer Factorization by Quantum Measurements

• URL: http://arxiv.org/abs/2309.10757v1
• Date: Tue, 19 Sep 2023 17:00:01 GMT
• Title: Integer Factorization by Quantum Measurements
• Authors: Giuseppe Mussardo and Andrea Trombettoni
• Abstract summary: Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on classical computers. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a quantum-time algorithm for integer factorization. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer $N$ is achieved in a number of steps equal to the number $k$ of its prime factors, -- e.g., if $N$ is the product of two primes, two quantum measurements are enough, regardless of the number of digits $n$ of the number $N$. Since $k$ is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.

Related papers

• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer. The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
  arXiv  Detail & Related papers  (2024-03-25T15:47:35Z)
• A generalized framework for quantum state discrimination, hybrid algorithms, and the quantum change point problem [3.4683494246563606]
  We present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. We give now-possible algorithms for the quantum change point identification problem which asks, given a sequence of quantum states, determine the time steps when the quantum states changed.
  arXiv  Detail & Related papers  (2023-12-07T03:42:40Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
  We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices. In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-12-23T15:36:59Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)
• Characterization of exact one-query quantum algorithms (ii): for partial functions [0.2741266294612775]
  The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity.
  arXiv  Detail & Related papers  (2020-08-27T09:06:34Z)
• Quadratic Sieve Factorization Quantum Algorithm and its Simulation [16.296638292223843]
  We have designed a quantum variant of the second fastest classical factorization algorithm named "Quadratic Sieve" We have constructed the simulation framework of quantized quadratic sieve algorithm using high-level programming language Mathematica.
  arXiv  Detail & Related papers  (2020-05-24T07:14:19Z)
• 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.