Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations
Tatsuki Odake1, Satoshi Yoshida1, Mio Murao1,2
1The University of Tokyo, Department of Physics, Graduate School of Science, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033, Japan.
Physical Review Letters
|December 19, 2025
Summary
This study establishes analytical lower bounds for the query complexity of unitary operations like inversion and conjugation. The findings demonstrate the optimality of existing protocols and reveal limitations for certain methods.
Area of Science:
- Quantum computing
- Linear algebra
- Information theory
Background:
- Unitary operations are fundamental in quantum computation.
- Efficient protocols for manipulating unknown unitary operations are crucial.
- Previous work established deterministic protocols for complex conjugation, inversion, and transposition.
Purpose of the Study:
- To establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation.
- To assess the optimality of existing deterministic exact protocols.
- To explore the possibility of catalytic protocols for unitary complex conjugation.
Main Methods:
- Derivation of analytical lower bounds using a novel differentiation framework.
- Analysis of query complexity for general differentiable functions f: SU(d) → SU(d).
- Extension of the framework to partially known and probabilistic settings.
Main Results:
- Established a lower bound of d^2 for unitary inversion, proving asymptotic optimality of O(d^2) inversion protocols.
- Demonstrated the impossibility of catalytic protocols for unitary complex conjugation.
- Extended the analysis to scenarios with partial knowledge and probabilistic outcomes.
Conclusions:
- The established lower bounds provide fundamental limits on the efficiency of manipulating unknown unitary operations.
- Deterministic exact inversion protocols are asymptotically optimal.
- Catalytic protocols are not viable for unitary complex conjugation, highlighting the unique challenges of this operation.
Related Concept Videos
01:30The Squeeze Theorem
252
Certain mathematical functions exhibit unpredictable or highly variable behavior near specific input values, making direct evaluation of their limits challenging. This complexity may arise from rapid oscillations or irregular patterns that obscure the function’s trend. In such cases, the Squeeze Theorem offers a reliable method for determining limits.According to the Squeeze Theorem, if a function is confined between two other functions near a particular point, and both outer functions...
252
00:59Propagation of Uncertainty from Random Error
1.6K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
1.6K
01:30Fundamental Theorem of Algebra
190
The Fundamental Theorem of Algebra is central to the study of polynomial equations, asserting that every non-constant polynomial with complex coefficients has at least one complex zero. This means that a polynomial of degree n ≥ 1, written as: with an ≠ 0, has at least one solution in the complex number system. Since the set of real numbers is a subset of complex numbers, this theorem applies equally to polynomials with real coefficients.Building on this result, the...
190
01:29Transformations of Functions II
119
Transformations in mathematics alter the position or orientation of a function’s graph while preserving its fundamental shape. One important type of transformation is the horizontal shift, which involves modifying the input variable within a function’s equation. This operation affects where outputs occur along the horizontal axis but does not alter the function’s overall structure.A horizontal shift is achieved by replacing the input variable x with either x + c or x - c,...
119
01:20Transformations of Functions III
147
Transformations modify the graphical representation of a function without changing its fundamental form. One common transformation is reflection, which flips the graph across a designated axis. When the vertical coordinates of all points are multiplied by the negative one, the entire graph is mirrored over the horizontal axis. This transformation reverses the vertical orientation of peaks and troughs, akin to signal inversion in electrical systems, where a waveform is flipped, but the timing of...
147
01:29Transformations of Functions I
144
A function's graph can be modified by changing its position or size without altering its overall shape. These transformations allow the graph to be moved across the coordinate plane while preserving its pattern and structure. One of the most common transformations is shifting, which repositions the graph without distorting it.When the output of a function is adjusted by adding or subtracting a constant, the graph shifts vertically. A positive value moves the graph upward, while a negative value...
144