On the Role of Coherence in Shor's Algorithm

• URL: http://arxiv.org/abs/2203.10632v1
• Date: Sun, 20 Mar 2022 19:49:17 GMT
• Title: On the Role of Coherence in Shor's Algorithm
• Authors: Felix Ahnefeld, Thomas Theurer, Dario Egloff, Juan Mauricio Matera, Martin B. Plenio
• Abstract summary: Shor's factoring algorithm provides a super-polynomial speed-up over all known classical factoring algorithms. We identify the role of coherence for this algorithm quantitatively.
• Score: 1.3124513975412255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shor's factoring algorithm provides a super-polynomial speed-up over all known classical factoring algorithms. Here, we address the question of which quantum properties fuel this advantage. We investigate a sequential variant of Shor's algorithm with a fixed overall structure and identify the role of coherence for this algorithm quantitatively. We analyze this protocol in the framework of dynamical resource theories, which capture the resource character of operations that can create and detect coherence. This allows us to derive a lower and an upper bound on the success probability of the protocol, which depend on rigorously defined measures of coherence as a dynamical resource. We compare these bounds with the classical limit of the protocol and conclude that within the fixed structure that we consider, coherence is the quantum resource that determines its performance by bounding the success probability from below and above. Therefore, we shine new light on the fundamental role of coherence in quantum computation.

Related papers

• A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees [15.259020859762556]
  We develop a framework aiming at designing quantum algorithms for optimization problems.<n>We provide theoretical guarantees on their approximation ratios.<n>We apply our framework to Max-Cut problem, implementing it as an adaptive variational quantum algorithm.
  arXiv  Detail & Related papers  (2025-12-25T15:38:24Z)
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm [8.412544270062323]
  We establish a link between the coherence fraction and the Bernstein-Vazirani algorithm.<n>We show that the success probability of the generalized Bernstein-Vazirani algorithm depends only on the coherence fraction of the initial state.<n>Our findings highlight how quantum coherence fraction influences the efficiency of quantum algorithms.
  arXiv  Detail & Related papers  (2025-11-10T08:41:23Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Converting entanglement into ensemble basis-free coherence [0.0]
  Coherence addresses the extent to which quantum properties are present in a given quantum system.<n>Measures of coherence for ensembles of quantum states remain an area of active research.<n>This paper presents two methods for generating ensemble coherence from a fixed amount of entanglement.
  arXiv  Detail & Related papers  (2025-06-02T21:32:11Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Quantum resources in Harrow-Hassidim-Lloyd algorithm [1.4605137432098108]
  We prove that nonvanishing quantum correlations, both bipartite and genuine multipartite entanglement, are required for solving nontrivial linear systems of equations. We find a nonvanishing l1-norm quantum coherence of the entire system and the register qubit which turns out to be related to the success probability of the algorithm.
  arXiv  Detail & Related papers  (2023-08-08T03:35:15Z)
• 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)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics [0.5249805590164902]
  We show that the algorithm scales similarly to the pure quantum version by deriving tight analytical lower bounds on its efficiency. We also study the behavior of the algorithm subject to noise, and find that under certain oracle and operational errors our measurement-based algorithm outperforms the standard algorithm.
  arXiv  Detail & Related papers  (2020-11-22T00:57:17Z)
• ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach [1.4873907857806357]
  We present a quantum circuit for estimating algorithmic complexity using the coding theorem method. As a use-case, an application framework for protein-protein interaction based on algorithmic complexity is proposed.
  arXiv  Detail & Related papers  (2020-09-18T14:41:41Z)
• Policies for elementary links in a quantum network [0.0]
  An important problem, especially for near-term quantum networks, is to develop optimal entanglement distribution protocols. We address this problem by initiating the study of quantum network protocols for entanglement distribution using the theory of decision processes. We show that the previously-studied memory-cutoff protocol can be phrased as a policy within our decision process framework.
  arXiv  Detail & Related papers  (2020-07-07T04:10:41Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)

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.