Improved Quantum Algorithms for Fidelity Estimation

• URL: http://arxiv.org/abs/2203.15993v1
• Date: Wed, 30 Mar 2022 02:02:16 GMT
• Title: Improved Quantum Algorithms for Fidelity Estimation
• Authors: Andr\'as Gily\'en, Alexander Poremba
• Abstract summary: We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
• Score: 77.34726150561087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficult to give good estimates of fidelity, especially when one works with mixed states over Hilbert spaces of very high dimension. Although, there has been some progress on fidelity estimation, all prior work either requires a large number of identical copies of the relevant states, or relies on unproven heuristics. In this work, we improve on both of these aspects by developing new and efficient quantum algorithms for fidelity estimation with provable performance guarantees in case at least one of the states is approximately low-rank. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation, as well as density matrix exponentiation and quantum spectral sampling. As a complementary result, we prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general, by giving a sample complexity lower bound that depends polynomially on the dimension. Moreover, if circuit descriptions for the relevant states are provided, we show that the task is hard for the complexity class called (honest verifier) quantum statistical zero knowledge via a reduction to a closely related result by Watrous.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Natural Stochastic Pairwise Coordinate Descent [6.187270874122921]
  Quantum machine learning through variational quantum algorithms (VQAs) has gained substantial attention in recent years. This paper introduces the quantum natural pairwise coordinate descent (2QNSCD) optimization method. We develop a highly sparse unbiased estimator of the novel metric tensor using a quantum circuit with gate complexity $Theta(1)$ times that of the parameterized quantum circuit and single-shot quantum measurements.
  arXiv  Detail & Related papers  (2024-07-18T18:57:29Z)
• 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)
• Quantification of Entanglement and Coherence with Purity Detection [16.01598003770752]
  Entanglement and coherence are fundamental properties of quantum systems, promising to power near future quantum technologies. Here, we demonstrate quantitative bounds to operationally useful entanglement and coherence. Our research offers an efficient means of verifying large-scale quantum information processing.
  arXiv  Detail & Related papers  (2023-08-14T11:03:40Z)
• Improved iterative quantum algorithm for ground-state preparation [4.921552273745794]
  We propose an improved iterative quantum algorithm to prepare the ground state of a Hamiltonian system. Our approach has advantages including the higher success probability at each iteration, the measurement precision-independent sampling complexity, the lower gate complexity, and only quantum resources are required when the ancillary state is well prepared.
  arXiv  Detail & Related papers  (2022-10-16T05:57:43Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• Testing symmetry on quantum computers [3.481985817302898]
  In quantum information and beyond, it is known that quantum states possessing symmetry are not useful for certain information-processing tasks. This paper details several quantum algorithms that test the symmetry of quantum states and channels.
  arXiv  Detail & Related papers  (2021-05-26T18:01:54Z)
• Experimental Realization of Nonadiabatic Holonomic Single-Qubit Quantum Gates with Two Dark Paths in a Trapped Ion [41.36300605844117]
  We show nonadiabatic holonomic single-qubit quantum gates on two dark paths in a trapped $171mathrmYb+$ ion based on four-level systems with resonant drives. We find that nontrivial holonomic two-qubit quantum gates can also be realized within current experimental technologies.
  arXiv  Detail & Related papers  (2021-01-19T06:57:50Z)
• Estimation of pure quantum states in high dimension at the limit of quantum accuracy through complex optimization and statistical inference [0.0]
  Quantum tomography has become a key tool for the assessment of quantum states, processes, and devices. In the case of mixed states of a single 2-dimensional quantum system adaptive methods have been recently introduced that achieve the theoretical accuracy limit deduced by Hayashi and Gill and Massar. Here we present an adaptive tomographic method and show through numerical simulations, that it is difficult to approach the fundamental accuracy of pure quantum states in high dimension.
  arXiv  Detail & Related papers  (2020-07-02T21:33:16Z)

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.