Entanglement and coherence in Bernstein-Vazirani algorithm

• URL: http://arxiv.org/abs/2205.13610v1
• Date: Thu, 26 May 2022 20:32:36 GMT
• Title: Entanglement and coherence in Bernstein-Vazirani algorithm
• Authors: Moein Naseri, Tulja Varun Kondra, Suchetana Goswami, Marco Fellous-Asiani, Alexander Streltsov
• Abstract summary: 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.
• Score: 58.720142291102135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum algorithms allow to outperform their classical counterparts in various tasks, most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such superposition can lead to entanglement across different qubits of the processors, there also exists quantum algorithms which outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this Letter, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. 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. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with arbitrary little amount of multipartite entanglement, general quantum correlations, and coherence.

Related papers

• Towards Entropic Constraints on Quantum Speedups [0.0]
  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.
  arXiv  Detail & Related papers  (2024-11-05T19:00:04Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Limitations of Noisy Quantum Devices in Computational and Entangling Power [5.178527492542246]
  We show that noisy quantum devices with a circuit depth of more than $O(log n)$ provide no advantages in any quantum algorithms. We also study the maximal entanglement that noisy quantum devices can produce under one- and two-dimensional qubit connections.
  arXiv  Detail & Related papers  (2023-06-05T12:29:55Z)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  We introduce an iterative quantum optimization algorithm to solve optimization problems. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement.
  arXiv  Detail & Related papers  (2023-03-09T18:59:37Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• 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)
• 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)
• 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)
• Quantum algorithmic differentiation [0.0]
  We present an algorithm to perform algorithmic differentiation in the context of quantum computing. We present two versions of the algorithm, one which is fully quantum and one which employees a classical step.
  arXiv  Detail & Related papers  (2020-06-23T22:52:22Z)
• 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.