Towards Entropic Constraints on Quantum Speedups

• URL: http://arxiv.org/abs/2411.03439v1
• Date: Tue, 05 Nov 2024 19:00:04 GMT
• Title: Towards Entropic Constraints on Quantum Speedups
• Authors: Jason Pollack, Dylan VanAllen,
• Abstract summary: Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks. Can we understand what fuels these speedups from an entropic perspective? Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm.
• Score: 0.0
• License:
• Abstract: Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks. Can we understand what fuels these speedups from an entropic perspective? Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm. The entanglement entropies for subsystems of a quantum state can be analyzed for subsystems of qubits in a quantum computer throughout the running of an algorithm. Here, a framework for making this entropic analysis is constructed, and performed on a selection of quantum circuits implementing known fast quantum algorithms and subroutines: Grover search, the quantum Fourier transform, and phase estimation. Our results are largely unsatisfactory: known entropy inequalities do not suffice to identify the presence or absence of quantum speedups. Although we know our algorithms must have quantum "magic", the Ingleton inequality, which holds for all entropies of subsystems of stabilizer states, is not violated in any of our examples. In some cases, however, monogamy of mutual information, which is obeyed for product states but violated for highly entangled bipartite states such as the $GHZ$ states, fails at some point in the course of our quantum circuits.

Related papers

• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• 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)
• Automated error correction in superdense coding, with implementation on superconducting quantum computer [0.28675177318965034]
  We present a task-specific error-correction technique that provides a complete protection over a restricted set of quantum states. Specifically, we give an automated error correction in Superdense Coding algorithms utilizing n-qubit generalized Bell states. We experimentally realize our automated error correction technique for three different types of superdense coding algorithm on a 7-qubit superconducting IBM quantum computer and also on a 27-qubit quantum simulator in the presence of noise.
  arXiv  Detail & Related papers  (2022-10-27T04:02:13Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• 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)
• Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
  We show that classical algorithms with sample and query (SQ) access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs. Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs.
  arXiv  Detail & Related papers  (2021-12-01T20:05:56Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48:00Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
  In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm. Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function.
  arXiv  Detail & Related papers  (2020-10-05T17:22:22Z)

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.