Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
Gily´ en and A
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
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.
fields
quant-ph 6representative citing papers
Quantum state isomorphism under group actions is BQP-hard for pure states across nontrivial groups and QSZK-complete for mixed states with finite groups; Pauli group version is BQP-complete and Clifford is GI-hard, ruling out efficient quantum algorithms for abelian mixed-state HS unless QSZK=BQP.
Quantum neural estimators achieve minimax-optimal copy complexity O(|Θ(U)| d / ε²) with sub-Gaussian concentration for measured Rényi relative entropies on density pairs with bounded Thompson metric.
QKAN is a quantum algorithmic framework using block-encodings and QSVT to implement wide-and-shallow networks for quantum learning and compositional state preparation.
A polynomial-time classical decision algorithm exactly characterizes which multivariable Laurent polynomial pairs are realizable by M-QSP and supplies a constructive implementation when the answer is yes.
A two-stage adaptive algorithm identifies a task-specific spectral cutoff to enable low-degree QSVT polynomials for nonlinear quantum property estimation, lowering cost versus conservative eigenvalue bounds.
citing papers explorer
-
Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
-
Quantum state isomorphism problems for groups
Quantum state isomorphism under group actions is BQP-hard for pure states across nontrivial groups and QSZK-complete for mixed states with finite groups; Pauli group version is BQP-complete and Clifford is GI-hard, ruling out efficient quantum algorithms for abelian mixed-state HS unless QSZK=BQP.
-
Performance Guarantees for Quantum Neural Estimation of Entropies
Quantum neural estimators achieve minimax-optimal copy complexity O(|Θ(U)| d / ε²) with sub-Gaussian concentration for measured Rényi relative entropies on density pairs with bounded Thompson metric.
-
QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
QKAN is a quantum algorithmic framework using block-encodings and QSVT to implement wide-and-shallow networks for quantum learning and compositional state preparation.
-
Polynomial time constructive decision algorithm for multivariable quantum signal processing
A polynomial-time classical decision algorithm exactly characterizes which multivariable Laurent polynomial pairs are realizable by M-QSP and supplies a constructive implementation when the answer is yes.
-
Adaptive identification of low-degree polynomials in quantum singular value transformation: application to nonlinear quantum properties estimation
A two-stage adaptive algorithm identifies a task-specific spectral cutoff to enable low-degree QSVT polynomials for nonlinear quantum property estimation, lowering cost versus conservative eigenvalue bounds.