Query-optimal estimation of unitary channels in diamond distance

Abstract

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a $\text{d}$-dimensional qudit, we aim to output a classical description of a unitary that is $\epsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\epsilon$ using $O({\text{d}}^2/\epsilon )$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O({\text{d}}^3/{\epsilon }^2)$ [via standard process tomography] or $O({\text{d}}^{2.5}/\epsilon )$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to "bootstrap" an algorithm that can produce constant-error estimates to one that can produce $\epsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega ({\text{d}}^2/\epsilon )$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

43 pages; v2, minor edits for referee comments

References in corpus (31)

• Quantum Algorithms Revisited
• Quantum state tomography via compressed sensing
• Distance measures to compare real and ideal quantum processes
• Theoretical framework for quantum networks
• A Theory of Trotter Error
• Quantum Circuits Architecture
• Local random quantum circuits are approximate polynomial-designs
• Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
• Gate Set Tomography
• Sample-optimal tomography of quantum states
• Optimal quantum learning of a unitary transformation
• Efficient use of quantum resources for the transmission of a reference frame
• Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations
• Parameter estimation of quantum channels
• Optimal estimation of group transformations using entanglement
• Quantum process tomography of unitary and near-unitary maps
• Optimal estimation of quantum dynamics
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Quantum reverse-engineering and reference frame alignment without non-local correlations
• Optimal quantum networks and one-shot entropies
• Optimal probabilistic storage and retrieval of unitary channels
• Shorter gate sequences for quantum computing by mixing unitaries
• Fast rate estimation of an unitary operation in SU(d)
• Optimal universal programming of unitary gates
• Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
• Efficient discrete-time simulations of continuous-time quantum query algorithms
• Entanglement assisted alignment of reference frames using a dense covariant coding
• Covariant quantum measurements may not be optimal
• Unitary-process discrimination with error margin
• Direct estimation of minimum gate fidelity
• Metric entropy of homogeneous spaces and Finsler geometry of classical Lie groups

Cited by in corpus (15)

• Learning quantum states and unitaries of bounded gate complexity
• The advantage of quantum control in many-body Hamiltonian learning
• Learning quantum states of continuous variable systems
• Quantum chi-squared tomography and mutual information testing
• Structure learning of Hamiltonians from real-time evolution
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Learning Quantum Processes with Quantum Statistical Queries
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• Agnostic Process Tomography
• Nearly query-optimal classical shadow estimation of unitary channels
• Parameterized quantum comb and simpler circuits for reversing unknown qubit-unitary operations
• Learning the structure of any Hamiltonian from minimal assumptions
• On the query complexity of unitary channel certification
• The symplectic rank of non-Gaussian quantum states
• Process Tomography for Clifford Unitaries