Benchmarks for quantum computers from Shor's algorithm

• URL: http://arxiv.org/abs/2111.13856v1
• Date: Sat, 27 Nov 2021 09:46:16 GMT
• Title: Benchmarks for quantum computers from Shor's algorithm
• Authors: E. D. Davis
• Abstract summary: Properties of Shor's algorithm and the related period-finding algorithm could serve as benchmarks for the operation of a quantum computer. Distinctive universal behaviour is expected for the probability for success of the period-finding as the input quantum register is increased.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Properties of Shor's algorithm and the related period-finding algorithm could serve as benchmarks for the operation of a quantum computer. Distinctive universal behaviour is expected for the probability for success of the period-finding algorithm as the input quantum register is increased through its critical size of $\mathfrak{m}_0=\lceil 2\log_2 r\rceil$ qubits (where $r$ is the period sought). Use of quadratic non-residues permits unequivocal predictions to be made about the outcome of the factoring algorithm.

Related papers

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Quantum Algorithm for Signal Denoising [32.77959665599749]
  The proposed algorithm is able to process textitboth classical and quantum signals. Numerical results show that it is efficient at removing noise of both classical and quantum origin.
  arXiv  Detail & Related papers  (2023-12-24T05:16:04Z)
• Scalable Algorithms for Power Function Calculations of quantum states in NISQ Era [7.2223563491914]
  This article focuses on the development of scalable and quantum bit-efficient algorithms for computing power functions of random quantum states. Two algorithms, based on Hadamard testing and Gate Set Tomography, are proposed.
  arXiv  Detail & Related papers  (2023-08-28T16:08:17Z)
• 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)
• An adaptive Bayesian quantum algorithm for phase estimation [0.0]
  We present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound.
  arXiv  Detail & Related papers  (2023-03-02T19:00:01Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03: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.