2025-11-28T20:49:18.679046

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

Odake, Yoshida, Murao
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.
academic

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

Basic Information

  • Paper ID: 2405.07625
  • Title: Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations
  • Authors: Tatsuki Odake, Satoshi Yoshida, Mio Murao (The University of Tokyo)
  • Classification: quant-ph (Quantum Physics)
  • Publication Date: November 27, 2025 (Version 4)
  • Paper Link: https://arxiv.org/abs/2405.07625

Abstract

This paper establishes analytical lower bounds on query complexity for transformations of unknown unitary operations. The research demonstrates that for inversion, transposition, and complex conjugation of d-dimensional unitary operations, there exist definite lower bounds even when the input unitary operation is a logarithmic-depth quantum circuit. In particular, the authors prove that unitary inversion requires at least d2d^2 queries, demonstrating that the existing O(d2)O(d^2) query algorithm is asymptotically optimal. The paper introduces an innovative differential-based framework to derive query complexity lower bounds for general differentiable functions f:SU(d)→SU(d)f: \mathrm{SU}(d)\to \mathrm{SU}(d), and proves that catalytic protocols are impossible for unitary complex conjugation. Furthermore, the framework extends to partially known and probabilistic settings.

Research Background and Motivation

Core Problem to Be Addressed

This paper investigates the query complexity of transformations of unknown unitary operations: given a black-box unitary operation U∈SU(d)U \in SU(d), how many queries to UU are required to implement a certain transformation f(U)f(U) (such as U−1U^{-1}, UTU^T, or U∗U^*)?

Importance of the Problem

  1. Fundamental Theory of Quantum Computing: This is a fundamental problem in quantum information processing, analogous to the role of the no-cloning theorem in quantum cryptography
  2. Practical Application Value:
    • Remote quantum computation: implementing transformations without knowing the specific details of unitary operations
    • Quantum control: eliminating unwanted Hamiltonian dynamics by implementing U−1U^{-1}
    • Quantum learning: measuring out-of-time-order correlation functions
    • Quantum singular value transformation: a core component of quantum algorithms
  3. Limitations of Existing Methods:
    • Missing analytical lower bounds: Except for unitary complex conjugation (lower bound d−1d-1) and certain nonlinear transformations, analytical lower bounds for most transformations are unknown
    • Limitations of numerical methods: For unitary inversion and transposition, only numerical lower bounds for d=2d=2 (equal to 4) are available, making generalization to arbitrary dimensions difficult
    • No-go theorems for parallel implementation: Existing no-go theorems only apply to parallel implementations; lower bounds for sequential implementations remain an open problem
    • Unknown conditions for catalytic protocols: It is unclear which transformations admit catalytic protocols (i.e., more efficient repeated execution after the first run)

Research Motivation

  1. Filling theoretical gaps: establishing a general analytical framework to prove query complexity lower bounds
  2. Verifying algorithm optimality: assessing whether existing algorithms achieve theoretical optimality
  3. Understanding resource requirements: characterizing the quantum resources needed for different transformations
  4. Guiding protocol design: providing theoretical guidance for improving existing protocols

Core Contributions

  1. Establishing a Universal Theoretical Framework: For the first time, proposes a differential-based method and establishes a semidefinite programming (SDP) framework for query complexity lower bounds for general differentiable functions f:SU(d)→SU(d)f: \mathrm{SU}(d) \to \mathrm{SU}(d)
  2. Proving Key Lower Bounds:
    • Unitary inversion: ≥d2\geq d^2 (proving the asymptotic optimality of the existing O(d2)O(d^2) algorithm)
    • Unitary transposition: ≥4\geq 4 (d=2d=2), ≥d+3\geq d+3 (d≥3d\geq 3)
    • Unitary complex conjugation: ≥d−1\geq d-1 (tight bound)
  3. Exponential Difficulty for Logarithmic-Depth Circuits: Proves that even when the input is restricted to logarithmic-depth nn-qubit unitary operations, these transformations still require exp⁡[Θ(n)]\exp[\Theta(n)] queries
  4. Impossibility of Catalytic Protocols: Provides necessary conditions for the existence of catalytic protocols (Theorem 4), proving that optimal catalytic algorithms do not exist for unitary complex conjugation and unitary iteration
  5. Framework Extensions:
    • Partially known setting: input unitary operations belong to a subgroup of SU(d)SU(d)
    • Probabilistic setting: transformations succeed with certain probability, establishing trade-off relations between query count and success probability

Detailed Methodology

Task Definition

Input: Black-box unitary operation U∈SU(d)U \in SU(d), which can be queried (used) in quantum circuits

Output: Implementing transformation f(U)f(U), where f:SU(d)→SU(d)f: SU(d) \to SU(d) is a given function (such as f(U)=U−1f(U)=U^{-1})

Objective: Finding the minimum number of queries NN (query complexity) required to implement f(U)f(U)

Constraints:

  • Deterministic and exact: can exactly implement f(U)f(U) for all U∈SU(d)U \in SU(d)
  • Fixed-order quantum circuit: using fixed quantum circuit structure (quantum comb)

Core Method Architecture

The paper's core innovation is the differential-based semidefinite programming framework, which consists of the following steps:

1. Quantum Circuit Representation (Figure S1)

Any NN-query quantum circuit implementing f(U)f(U) can be represented as: Z(U):=VN+1∏j=1N(U⊗I)VjZ(U) := V_{N+1} \prod_{j=1}^N (U \otimes I)V_j

where V1,…,VN+1V_1, \ldots, V_{N+1} are fixed unitary operations, and ρA=∣0⟩⟨0∣\rho_A = |0\rangle\langle 0| is the initial state of the auxiliary system.

2. Key Equation Derivation

By performing perturbation U=eiϵHU0U = e^{i\epsilon H}U_0 near U0U_0 and taking derivatives with respect to ϵ\epsilon, we obtain:

Zeroth-order condition (ϵ=0\epsilon=0): V~N+1(U0)∏j=1N(U0⊗I)Vj[∣ψ⟩⊗∣0⟩]=∣ψ⟩⊗∣0⟩\tilde{V}_{N+1}(U_0) \prod_{j=1}^N (U_0 \otimes I)V_j [|\psi\rangle \otimes |0\rangle] = |\psi\rangle \otimes |0\rangle

First-order condition (derivative with respect to ϵ\epsilon): ∑s=1N∑jMj,0(s,right)(U0)†HMj,0(s,left)(U0)=gU0(H)+αU0(H)I\sum_{s=1}^N \sum_j M_{j,0}^{(s,right)}(U_0)^\dagger H M_{j,0}^{(s,left)}(U_0) = g_{U_0}(H) + \alpha_{U_0}(H)I

where gU0g_{U_0} is the derivative map of ff at U0U_0: gU0(H):=−iddϵ∣ϵ=0[f(U0)−1f(eiϵHU0)]g_{U_0}(H) := -i \frac{d}{d\epsilon}\Big|_{\epsilon=0} [f(U_0)^{-1}f(e^{i\epsilon H}U_0)]

3. Complete Positivity Constraint

Define the linear map: EU0(H)=∑s=1N∑jMj,0(s,left)(U0)†HMj,0(s,left)(U0)\mathcal{E}_{U_0}(H) = \sum_{s=1}^N \sum_j M_{j,0}^{(s,left)}(U_0)^\dagger H M_{j,0}^{(s,left)}(U_0)

Key properties:

  • EU0(I)=NI\mathcal{E}_{U_0}(I) = NI
  • EU0(H)=gU0(H)+αU0(H)I\mathcal{E}_{U_0}(H) = g_{U_0}(H) + \alpha_{U_0}(H)I for H∈su(d)H \in su(d)
  • EU0\mathcal{E}_{U_0} must be a completely positive (CP) map

4. Choi Operator and SDP

Using the Choi-Jamiołkowski isomorphism, the complete positivity condition is transformed into a semidefinite condition: JEU0=JgU0+βU0⊗I≥0J_{\mathcal{E}_{U_0}} = J_{g_{U_0}} + \beta_{U_0} \otimes I \geq 0

where the Choi operator is defined as: JgU0:=∑j=1d2−1Gj∗⊗gU0(Gj)J_{g_{U_0}} := \sum_{j=1}^{d^2-1} G_j^* \otimes g_{U_0}(G_j)

{Gj}\{G_j\} is an orthonormal basis of su(d)su(d).

Main Theorem (Theorem 1)

For any differentiable function f:SU(d)→SU(d)f: SU(d) \to SU(d), the query complexity is at least the solution to the following SDP:

\min \quad & \text{tr}\beta_{U_0} \\ \text{s.t.} \quad & \beta_{U_0} \in \mathcal{L}(\mathbb{C}^d) \\ & J_{g_{U_0}} + \beta_{U_0} \otimes I \geq 0 \end{aligned}$$ ### Technical Innovations 1. **Introduction of Differential Method**: - Traditional methods (polynomial degree analysis, Fourier series analysis) struggle with sequential implementations - The differential method only requires local information (behavior near $U_0$), avoiding the complexity of global analysis - Key insight: the circuit must work correctly near all $U_0$ 2. **Choi Operator Technique**: - Transforms the complete positivity of quantum operations into semidefiniteness of matrices - Makes the problem solvable using standard SDP solvers 3. **Handling Logarithmic-Depth Circuits**: - Proves that lower bounds still hold even when input is restricted to logarithmic-depth unitary operations - Exploits the fact that Pauli rotations can be implemented with logarithmic depth - Since SDP constraints depend only on local differential information 4. **Haar Averaging Technique** (proof of Corollary 3): - Takes Haar average of constraints over all $U_0$ - Exploits symmetry to simplify constraints - Obtains tighter lower bounds ## Experimental Setup This is a **purely theoretical research** paper with no experimental verification, relying primarily on mathematical proofs and SDP solving to establish lower bounds. ### SDP Solving 1. **Analytical Solution**: For unitary inversion, transposition, and complex conjugation, the paper solves the SDP analytically 2. **Numerical Verification**: Uses SDP solvers to verify that results for $d=2$ are consistent with known numerical lower bounds ### Verification Methods 1. **Tightness Verification**: Comparing lower bounds with known algorithm upper bounds 2. **Dual Problem**: Constructing dual SDP to verify correctness of the primal problem (Appendix E) 3. **Special Case Checking**: Verifying known results (e.g., unitary inversion requires 4 queries for $d=2$) ## Experimental Results ### Main Results (Table I) | Transformation | Lower Bound (This Work) | Known Optimal Algorithm | |---|---|---| | $f(U)=U^{-1}$ | $d^2$ | $4$ ($d=2$), $\sim (\pi/2)d^2$ ($d\geq 3$) | | $f(U)=U^T$ | $4$ ($d=2$), $d+3$ ($d\geq 3$) | $4$ ($d=2$), $\sim (\pi/2)d^2$ ($d\geq 3$) | | $f(U)=U^*$ | $d-1$ | $d-1$ | **Key Findings**: 1. **Asymptotic Optimality of Unitary Inversion**: - Lower bound: $d^2$ - Upper bound: $O(d^2)$ (from reference [19]) - Conclusion: Existing algorithms are asymptotically optimal! 2. **Tight Bound for Unitary Complex Conjugation**: - Lower bound $d-1$ exactly matches known algorithms - This provides an alternative proof of known results 3. **Room for Improvement in Unitary Transposition**: - Lower bound: $O(d)$ - Upper bound: $O(d^2)$ - Conclusion: More efficient algorithms may exist ### Exponential Difficulty for Logarithmic-Depth Circuits (Corollary 2) For $n$-qubit systems ($d=2^n$), even when input is restricted to logarithmic-depth unitary operations: - Unitary inversion: $\geq \exp[\Omega(n)]$ - Unitary transposition: $\geq \exp[\Omega(n)]$ - Unitary complex conjugation: $\geq \exp[\Omega(n)]$ **Significance**: Even for "simple" inputs, these transformations are inherently difficult. ### Impossibility of Catalytic Protocols (Theorem 4) **Theorem Statement**: If the SDP solution $N$ is tight for functions $f$ satisfying $f(U_0)=I$, then no optimal catalytic algorithm exists. **Applications**: 1. **Unitary Complex Conjugation**: Lower bound $d-1$ is tight → no catalytic protocol exists 2. **Unitary Iteration** $U \mapsto U^n$: Lower bound $n$ is tight → no catalytic protocol exists **Counterexample**: - Unitary inversion: SDP solution $d^2-1$ is not tight (true lower bound $d^2$) → catalytic protocol may exist - In fact, a catalytic protocol does exist for $d=2$ [18] ### Trade-off for Probabilistic Transformations (Theorem S7) For probabilistic unitary transposition, the success probability upper bound is: $$p_{\text{trans}}(U_0) \leq \left(\frac{d}{((d^2-1)/N)+1}\right)^2$$ **Special Cases**: - $N=1$: $p \leq 1/d^2$ (consistent with known results [12]) - $N \to \infty$: $p \to 1$ **Figure 2** shows success probability upper bounds for different query counts, revealing: 1. Success probability monotonically increases with query count 2. For fixed $N$, $p \to 0$ as $d \to \infty$ ### Partially Known Setting For unitary inversion with input restricted to $SO(d) \subset SU(d)$: - Lower bound: $d-1$ ($d=2$ is tight) - Significantly lower than the general case ($d^2$) **Insight**: Partial knowledge can substantially reduce query complexity. ## Related Work ### No-go Theorems for Quantum State Transformations 1. **No-cloning theorem** [1]: Cannot clone unknown quantum states 2. **Probabilistic cloning** [3]: Optimal fidelity is bounded 3. **Quantum entanglers** [5]: Limitations of universal quantum gates ### Transformations of Unitary Operations 1. **Single-query no-go theorems** [11,27]: Many transformations cannot be implemented with a single query 2. **Probabilistic and approximate protocols** [6,7,11-17,27,32-43]: - Probabilistic unitary inversion [13] - Approximate unitary reset [7,14,16,17] - Universal quantum programming [6,31] 3. **Deterministic exact protocols** (recent breakthroughs): - Unitary complex conjugation: $d-1$ queries [44] - Unitary inversion: $4$ queries ($d=2$) [18], $O(d^2)$ queries (general $d$) [19] - Unitary transposition: $4$ queries ($d=2$) [45] ### Query Complexity Lower Bounds 1. **Polynomial degree method** [12]: - Unitary inversion: $\geq d-1$ - Unitary transposition: $\geq 2$ - Limitation: bounds are too loose 2. **Numerical methods** [18,45]: - Only applicable to small dimensions ($d=2$) - Difficult to generalize 3. **No-go theorems for parallel implementation** [12]: Not applicable to sequential implementations ### Advantages of This Work 1. **General framework**: Applicable to arbitrary differentiable functions $f$ 2. **Tighter lower bounds**: Particularly for unitary inversion ($d^2$ vs. $d-1$) 3. **Scalability**: Easily extends to partially known and probabilistic settings 4. **Novel technique**: Differential method provides new tools for the field ## Conclusions and Discussion ### Main Conclusions 1. **Theoretical Contribution**: Establishes a universal differential-based framework characterizing query complexity lower bounds through SDP 2. **Specific Results**: - Unitary inversion: $\geq d^2$ (asymptotically tight) - Unitary transposition: $\geq d+3$ ($d \geq 3$) - Unitary complex conjugation: $\geq d-1$ (tight) 3. **Algorithm Optimality**: Proves the optimality of existing unitary inversion algorithms [18,19] 4. **Catalytic Protocols**: Provides sufficient conditions for the non-existence of catalytic protocols 5. **Robustness**: Lower bounds hold even for logarithmic-depth inputs ### Limitations 1. **SDP Relaxation**: - For unitary inversion, the SDP solution $d^2-1$ requires additional arguments to upgrade to $d^2$ - For unitary transposition, the gap between lower bound $d+3$ and upper bound $O(d^2)$ remains 2. **First-Order Differential Limitation**: - Only considers first-order derivative information - Higher-order derivatives may yield tighter bounds (mentioned by authors in discussion) 3. **Analysis at Specific $U_0$**: - SDP provides local conditions at specific $U_0$ - Requires additional techniques (such as Haar averaging) to obtain global lower bounds 4. **Conservatism in Probabilistic Setting**: - Upper bounds on success probability in Theorem S8 may not be tight - Only exploits local information ### Future Directions 1. **Higher-Order Differential Extensions**: - Consider second and higher-order derivatives - May yield tighter lower bounds 2. **Combinatorial Methods**: - Combine differential method with polynomial degree method - May produce stronger no-go theorems 3. **Optimization of Unitary Transposition**: - Seek $O(d)$ query algorithms (matching lower bounds) - Or prove higher lower bounds 4. **Necessary and Sufficient Conditions for Catalytic Protocols**: - Theorem 4 only provides necessary conditions - Seek sufficient conditions or complete characterization 5. **Application to Other Transformations**: - Apply framework to other unitary transformations (such as quantum singular value transformation) - Explore more applications in partially known settings ## In-Depth Evaluation ### Strengths 1. **Strong Method Innovation**: - First systematic application of differential method to query complexity analysis - Elegant and powerful combination of Choi operator and SDP - Provides new analytical tools for the field 2. **Significant Theoretical Contributions**: - Resolves long-standing open problems (lower bounds for unitary inversion) - Proves optimality of existing algorithms - Establishes universal framework rather than problem-specific solutions 3. **Profound Results**: - Exponential difficulty for logarithmic-depth circuits is surprising - Impossibility of catalytic protocols provides new insights - Probabilistic trade-off relations have practical value 4. **Technical Rigor**: - Complete and rigorous proofs (main results in text, technical details in supplementary material) - Considers multiple generalizations (partially known, probabilistic) - Verification through dual SDP 5. **Clear Presentation**: - Well-structured, progressing logically from motivation to results - Precise mathematical exposition - Effective information conveyance through tables (especially Table I) and figures (especially Figure 2) ### Weaknesses 1. **Limited Tightness of Lower Bounds**: - Larger gap for unitary transposition ($O(d)$ vs. $O(d^2)$) - Suggests room for method improvement 2. **High Technical Complexity**: - Requires strong background in operator theory and SDP - May limit accessibility of the method 3. **Absence of Experimental Verification**: - While theoretical work, could include more numerical experiments - For example, numerical computation of SDP solutions for various dimensions $d$ 4. **Insufficient Discussion of Applications**: - Could elaborate more on implications for quantum algorithm design - Limited description of practical applications of partially known settings 5. **Limited Comparison with Related Work**: - Could provide more detailed comparison of different methods (differential vs. polynomial degree) - Discussion of concurrent work [55] is relatively brief ### Impact 1. **Theoretical Impact**: - Provides new paradigm for query complexity research - Expected to be widely cited and extended in subsequent work - Concurrent work [54] already employs similar techniques 2. **Practical Value**: - Guides quantum algorithm design (knowing what is impossible) - Helps evaluate efficiency of existing protocols - Provides resource estimates for hardware implementation 3. **Reproducibility**: - Theoretical proofs are verifiable - SDP implementable with standard solvers - Comprehensive supplementary material (37 pages) ### Applicable Scenarios 1. **Quantum Algorithm Design**: - Evaluate query complexity of new algorithms - Decide whether seeking better algorithms is worthwhile 2. **Quantum Control**: - Understand resource requirements for eliminating unwanted dynamics - Design efficient quantum error correction protocols 3. **Quantum Learning**: - Understand fundamental limitations of learning quantum dynamics - Optimize quantum process tomography schemes 4. **Theoretical Research**: - Tool for studying other quantum information tasks - Extension to other group structures (subgroups of unitary group) ## Selected References **Foundational No-go Theorems**: - [1] Wootters & Zurek (1982): No-cloning theorem - [2] Bennett & Brassard (2014): Quantum cryptography **Transformations of Unitary Operations**: - [12] Quintino et al. (2019): Probabilistic unitary transformations - [13] Quintino et al. (2019): Unitary inversion - [18] Yoshida et al. (2023): Deterministic exact qubit unitary inversion - [19] Chen et al. (2024): $O(d^2)$ query unitary inversion - [44] Miyazaki et al. (2019): Unitary complex conjugation **Technical Tools**: - [46] Chiribella et al. (2008): Quantum circuit architecture (quantum comb) - [50,51] Choi, Jamiołkowski: Choi-Jamiołkowski isomorphism **Concurrent Work**: - [54] Bavaresco et al. (2025): Computational complexity of quantum switches - [55] Chen et al. (2025): Lower bounds for approximate unitary inversion --- **Overall Assessment**: This is a **high-quality theoretical quantum information paper** that proposes innovative methodology, resolves important open problems, and establishes a universal analytical framework. While certain lower bounds could be tighter, the technical contributions and theoretical insights are sufficiently significant. This work is expected to have lasting impact on quantum algorithms and quantum complexity theory.