Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations

Abstract

Recent developments have revealed deterministic and exact protocols for performing complex conjugation, inversion, and transposition of a general $d$-dimensional unknown unitary operation using a finite number of queries to a black-box unitary operation. In this work, we establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation, which hold even if the input unitary is an unknown logarithmic-depth unitary. Specifically, our lower bound of $d^2$ for unitary inversion demonstrates the asymptotic optimality of the deterministic exact inversion protocol, which operates with $O(d^2)$ queries. We introduce a novel framework utilizing differentiation to derive these lower bounds on query complexity for general differentiable functions $f:\mathrm{SU}(d)\to \mathrm{SU}(d)$. As a corollary, we prove that a catalytic protocol -- a new concept recently noted in the study of exact unitary inversion -- is impossible for unitary complex conjugation. Furthermore, we extend our framework to the partially known setting, where the input unitary operation is promised to be within a subgroup of $\mathrm{SU}(d)$ and the probabilistic setting, where transformations succeed probabilistically.

21 pages, 7 figures

References in corpus (36)

• Quantum cryptography: Public key distribution and coin tossing
• A bound on chaos
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Measuring out-of-time-order correlations and multiple quantum spectra in a trapped ion quantum magnet
• Quantum Circuits Architecture
• Measuring out-of-time-order correlators on a nuclear magnetic resonance quantum simulator
• Probabilistic Quantum Teleportation
• Optimal quantum learning of a unitary transformation
• Quantum circuits cannot control unknown operations
• Quantum process tomography of unitary and near-unitary maps
• Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
• Optimal cloning of unitary transformations
• Optimal quantum networks and one-shot entropies
• Optimal probabilistic storage and retrieval of unitary channels
• Theoretical framework for Higher-Order Quantum Theory
• Probabilistic exact universal quantum circuits for transforming unitary operations
• Optimal universal programming of unitary gates
• Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality
• Resetting uncontrolled quantum systems
• Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly
• Universal super-replication of unitary gates
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• Deterministic superreplication of one-parameter unitary transformations
• Quantum conditional operations
• Success-or-Draw: A Strategy Allowing Repeat-Until-Success in Quantum Computation
• Optimal processing of reversible quantum channels
• A universal quantum rewinding protocol with an arbitrarily high probability of success
• Translating Uncontrolled Systems in Time
• Probabilistic storage and retrieval of qubit phase gates
• Optimal universal quantum circuits for unitary complex conjugation
• No-iteration of unknown quantum gates
• Linear programming with unitary-equivariant constraints
• Topological obstructions to quantum computation with unitary oracles
• Simulating the quantum switch with quantum circuits is computationally hard
• Parameterized quantum comb and simpler circuits for reversing unknown qubit-unitary operations