Quantum Algorithm for Fidelity Estimation
- URL: http://arxiv.org/abs/2103.09076v2
- Date: Thu, 29 Sep 2022 03:44:45 GMT
- Title: Quantum Algorithm for Fidelity Estimation
- Authors: Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi
Liu, Mingsheng Ying
- Abstract summary: For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem.
We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
- Score: 8.270684567157987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For two unknown mixed quantum states $\rho$ and $\sigma$ in an
$N$-dimensional Hilbert space, computing their fidelity $F(\rho,\sigma)$ is a
basic problem with many important applications in quantum computing and quantum
information, for example verification and characterization of the outputs of a
quantum computer, and design and analysis of quantum algorithms. In this paper,
we propose a quantum algorithm that solves this problem in
$\operatorname{poly}(\log (N), r, 1/\varepsilon)$ time, where $r$ is the lower
rank of $\rho$ and $\sigma$, and $\varepsilon$ is the desired precision,
provided that the purifications of $\rho$ and $\sigma$ are prepared by quantum
oracles. This algorithm exhibits an exponential speedup over the best known
algorithm (based on quantum state tomography) which has time complexity
polynomial in $N$.
Related papers
- A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
We introduce a novel quantum XZ24 algorithm, designed for efficiently computing the eigen-energy spectra of any quantum systems.
Compared to existing quantum methods, the new algorithm stands out for its remarkably low measurement cost.
We anticipate that the new algorithm will drive significant progress in quantum system simulation and offer promising applications in quantum computing and quantum information processing.
arXiv Detail & Related papers (2024-06-01T04:31:43Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - 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) - Time-Efficient Quantum Entropy Estimator via Samplizer [8.646488471216262]
Estimating the entropy of a quantum state is a basic problem in quantum information.
We introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(rho)$ and R'enyi entropy $S_alpha(rho)$.
arXiv Detail & Related papers (2024-01-18T12:50:20Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.
This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
arXiv Detail & Related papers (2023-11-17T20:38:38Z) - Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions.
We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
arXiv Detail & Related papers (2023-09-19T22:53:17Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
For networks with $n$ nodes, the fastest known algorithms run in time $O(cn)$ in the worst case, with no improvement in two decades.
Inspired by recent advances in quantum computing, we ask whether BNSL admits a quantum speedup.
We give two algorithms achieving $c leq 1.817$ and $c leq 1.982$.
arXiv Detail & Related papers (2023-05-31T09:15:28Z) - Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
We propose efficient quantum algorithms for estimating the trace distance within additive error $varepsilon$ between mixed quantum states of rank $r$.
We show that the decision version of low-rank trace distance estimation is $mathsfBQP$-complete.
arXiv Detail & Related papers (2023-01-17T10:16:14Z) - 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) - Quantum $k$-nearest neighbors algorithm [0.0]
We present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure.
Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data.
arXiv Detail & Related papers (2020-03-20T10:48:57Z)
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.