Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.09629

A short note on the 0-fidelity

Karl Mayer

Published Sep 20, 2021• 0 citations
arXivHTMLPDF

Abstract

A recent article introduced a hierarchy of quantities called $k$-fidelities that approximate the quantum process fidelity with increasing accuracy. The lowest approximation in this hiearchy is the $0$-fidelity. The authors gave a protocol for estimating the $0$-fidelity and showed numerical evidence that it approximates the process fidelity. In this note, we prove lower and upper bounds on the process fidelity as linear functions of the 0-fidelity. By solving a semidefinite program, we provide evidence that the lower bound is tight.

DOI
10.48550/arxiv.2109.09629

Related papers

Efficient assessment of process fidelity

Sean Greenaway, Frédéric Sauvage, Kiran E. Khosla +1 more

The accurate implementation of quantum gates is essential for the realization of quantum algorithms and digital quantum simulations. This accuracy may be increased on noisy hardware through the variational optimization of gates, however the experimental realization of such a protocol is impeded by the large effort required to estimate the fidelity of an implemented gate. With a hierarchy of approximations we find a faithful approximation to the quantum process fidelity that can be estimated experimentally with reduced effort. Its practical use is demonstrated with the optimization of a three-qubit quantum gate on a commercially available quantum processor.

arXiv:2102.08101•Physical Review Research•Jul 7, 2021•15 citations

Quantum process fidelity bounds from sets of input states

Karl Mayer, Emanuel H. Knill

We investigate the problem of bounding the quantum process fidelity given bounds on the fidelities between target states and the action of a process on a set of pure input states. We formulate the problem as a semidefinite program and prove convexity of the minimum process fidelity as a function of the errors on the output states. We characterize the conditions required to uniquely determine a process in the case of no errors and derive a lower bound on its fidelity in the limit of small errors for any set of input states satisfying these conditions. We then consider sets of input states whose one-dimensional projectors form a symmetric positive operator-valued measure (POVM). We prove that for such sets the minimum fidelity is bounded by a linear function of the average output state error. A symmetric POVM with minimal number of elements contains $d+1$ states, where $d$ is the Hilbert space dimension. Our bounds applied to such states provide an efficient method for estimating the process fidelity without the use of full process tomography.

arXiv:1805.04491•Physical Review A•Nov 21, 2018•18 citations

Application of SDP to product rules and quantum query complexity

Mittal, Rajat

In recent years, semidefinite programming has played a vital role in shaping complexity theory and quantum computing. There have been numerous applications ranging from estimating quantum values, over approximating combinatorial quantities, to proving various bounds. This work extends the use of semidefinite programs (SDPs) to proving product rules and to characterizing quantum query complexity. In the first application, we provide a general framework to establishing product rules for quantities that can be expressed (or approximated) using SDPs. We use duality theory to give product rules, which bound the value of the ``product'' of two problems in terms of their value. Some previous results have implicitly used the properties of SDPs to give such product rules. Here we give sufficient and necessary conditions under which these approaches work, thereby enabling us to capture these previous results under our unified framework. We also include a discussion about alternate definitions of what a ``product'' means and how they fit into our approach. The second application provides an SDP characterization of quantum query complexity, which is one of the ways in which complexity of a function can be measured. It is known that quantum query complexity can be lower bounded by the so-called ``adversary method'' which is expressible as a semidefinite program. Recently, Ben Reichardt showed that the adversary method leads to a tight lower bound for boolean functions by converting the solution of this SDP (of adversary method) into an algorithm. We show that a related SDP, called ``witness size'' in this thesis, provides a tight bound on the quantum query complexity of non boolean functions (total as well as partial). This witness size SDP is also used to give composition results for quantum query complexity. We also show that the witness size is bounded by a constant multiple of the adversary bound. Finally, we briefly explore whether other convex programming paradigms can be useful in complexity theory. One of them is copositive programming. We show that one of the recent result about parallel repetition of unique games, by Barak et.al., can be interpreted as an application of copositive programming.

•Jan 1, 2011•0 citations

A note on the measures of process fidelity for non-unitary quantum operations

Joydip Ghosh

Various fidelity measures can be defined between two quantum processes especially when at least one of them is non-unitary. In this paper we consider two such measures of state averaged process fidelity, put forward an efficient procedure to compute them and investigate their mathematical properties as well as their relationship.

arXiv:1111.2478•Nov 10, 2011•9 citations

Quantum SDP-Solvers: Better Upper and Lower Bounds

Joran van Apeldoorn, András Gilyén, Sander Gribling +1 more

Brandao and Svore recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m is approximately n, which is the same as classical.

Annual Symposium on Foundations of Computer Science•Oct 1, 2017•57 citations

Comment on “Compare Quantum Operation Sensitivity for Different Distance Measures"

Gao Yun-feng, Jian Qiang Feng

We make comments on the conclusions of the paper: “Compare Quantum Operation Sensitivity for Different Distance Measures" [ Commun. Theor. Phys. 53 (2010) 635 ], and give a physical example to describe the non-equivalence of the fidelity and the trace distance. We prove that the fidelity is not more sensitive to a quantum operation than the trace distance.

Communications in Theoretical Physics•Nov 1, 2011•0 citations
A recent article introduced a hierarchy of quantities called kkk-fidelities that approximate the quantum process fidelity with increasing accuracy. The lowest approximation in this hiearchy is the 000-fidelity. The authors gave a protocol for estimating the 000-fidelity and showed numerical evidence that it approximates the process fidelity. In this note, we prove lower and upper bounds on the process fidelity as linear functions of the 0-fidelity. By solving a semidefinite program, we provide evidence that the lower bound is tight.
The accurate implementation of quantum gates is essential for the realization of quantum algorithms and digital quantum simulations. This accuracy may be increased on noisy hardware through the variational optimization of gates, however the experimental realization of such a protocol is impeded by the large effort required to estimate the fidelity of an implemented gate. With a hierarchy of approximations we find a faithful approximation to the quantum process fidelity that can be estimated experimentally with reduced effort. Its practical use is demonstrated with the optimization of a three-qubit quantum gate on a commercially available quantum processor.
We investigate the problem of bounding the quantum process fidelity given bounds on the fidelities between target states and the action of a process on a set of pure input states. We formulate the problem as a semidefinite program and prove convexity of the minimum process fidelity as a function of the errors on the output states. We characterize the conditions required to uniquely determine a process in the case of no errors and derive a lower bound on its fidelity in the limit of small errors for any set of input states satisfying these conditions. We then consider sets of input states whose one-dimensional projectors form a symmetric positive operator-valued measure (POVM). We prove that for such sets the minimum fidelity is bounded by a linear function of the average output state error. A symmetric POVM with minimal number of elements contains d+1d+1d+1 states, where ddd is the Hilbert space dimension. Our bounds applied to such states provide an efficient method for estimating the process fidelity without the use of full process tomography.
In recent years, semidefinite programming has played a vital role in shaping complexity theory and quantum computing. There have been numerous applications ranging from estimating quantum values, over approximating combinatorial quantities, to proving various bounds. This work extends the use of semidefinite programs (SDPs) to proving product rules and to characterizing quantum query complexity. In the first application, we provide a general framework to establishing product rules for quantities that can be expressed (or approximated) using SDPs. We use duality theory to give product rules, which bound the value of the ``product'' of two problems in terms of their value. Some previous results have implicitly used the properties of SDPs to give such product rules. Here we give sufficient and necessary conditions under which these approaches work, thereby enabling us to capture these previous results under our unified framework. We also include a discussion about alternate definitions of what a ``product'' means and how they fit into our approach. The second application provides an SDP characterization of quantum query complexity, which is one of the ways in which complexity of a function can be measured. It is known that quantum query complexity can be lower bounded by the so-called ``adversary method'' which is expressible as a semidefinite program. Recently, Ben Reichardt showed that the adversary method leads to a tight lower bound for boolean functions by converting the solution of this SDP (of adversary method) into an algorithm. We show that a related SDP, called ``witness size'' in this thesis, provides a tight bound on the quantum query complexity of non boolean functions (total as well as partial). This witness size SDP is also used to give composition results for quantum query complexity. We also show that the witness size is bounded by a constant multiple of the adversary bound. Finally, we briefly explore whether other convex programming paradigms can be useful in complexity theory. One of them is copositive programming. We show that one of the recent result about parallel repetition of unique games, by Barak et.al., can be interpreted as an application of copositive programming.
Brandao and Svore recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m is approximately n, which is the same as classical.