Unknown unitary inversion is a fundamental primitive in quantum computing and physics. Although recent work has demonstrated that quantum algorithms can invert arbitrary unknown unitaries without accessing their classical descriptions, improving the efficiency of such protocols remains an open question. In this work, we present efficient quantum algorithms for inverting unitaries with specific Hamiltonian structures, achieving significant reductions in both ancilla qubit requirements and unitary query complexity. We identify cases where unitaries encoding exponentially many parameters can be inverted using only a single query. We further extend our framework to implement unitary complex conjugation and transposition operations, and develop modified protocols capable of inverting more general classes of Hamiltonians. We have also demonstrated the efficacy and robustness of our algorithms via numerical simulations under realistic noise conditions of superconducting quantum hardware. Our results establish more efficient protocols that improve the resources required for quantum unitary inversion when prior information about the quantum system is available, and provide practical methods for implementing these operations on near-term quantum devices.
Unknown unitary inversion is a fundamental primitive in quantum computing and physics. Although recent work has demonstrated that quantum algorithms can invert arbitrary unknown unitaries without accessing their classical descriptions, improving the efficiency of such protocols remains an open question. In this work, we present efficient quantum algorithms for inverting unitaries with specific Hamiltonian structures, achieving significant reductions in both ancilla qubit requirements and unitary query complexity. We identify cases where unitaries encoding exponentially many parameters can be inverted using only a single query. We further extend our framework to implement unitary complex conjugation and transposition operations, and develop modified protocols capable of inverting more general classes of Hamiltonians. We have also demonstrated the efficacy and robustness of our algorithms via numerical simulations under realistic noise conditions of superconducting quantum hardware. Our results establish more efficient protocols that improve the resources required for quantum unitary inversion when prior information about the quantum system is available, and provide practical methods for implementing these operations on near-term quantum devices.
Reversing unknown quantum dynamics is vital for quantum control and learning, yet full unitary inversion requires a resource-intensive O(d2) queries. Because many applications only require the reversed evolution for a given observable, a critical gap remains in understanding the minimal resources for such targeted reversal. Here, we address this by introducing shadow unitary inversion. We establish a lower bound showing the query complexity must scale at least linearly with system dimension for spectrally biased observables, with the constant determined by the observable’s spectral properties. For qubit case, we construct an explicit, deterministic three-query sequential protocol achieving exact shadow inversion and completely characterize all admissible channels, with numerical evidence suggesting optimality. For higher dimensions, we develop a semidefinite-programming formulation and introduce a representation-theoretic symmetry reduction that decomposes the optimization into invariant blocks, substantially reducing the problem size. Shadow unitary inversion thus offers a resource-efficient path to inverse-dynamics estimation for future quantum control, diagnostics, and learning tasks. Reversing unitary operations is crucial in quantum computing and control, yet remains a challenging task. The authors introduce shadow unitary inversion, achieving efficient inversion at the expectation value level with reduced query complexity, offering a promising approach for quantum error correction and information recovery.
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 Letter, 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: SU(d)→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 SU(d) and the probabilistic setting, where transformations succeed probabilistically.
Estimating the unitarity of an unknown quantum channelEprovides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that useO(ϵ−2)andO(d⋅ϵ−2)calls toEwith coherent and incoherent accesses, respectively, wheredis the dimension of the system thatEacts on and$\epsilon istherequiredprecision.Wefurthershowthatboththed−dependenceand\epsilon −dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound\Omega (\sqrt {d}),improvingthepriorbestlowerbound\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).
Quantum algorithms for diverse problems, including search and optimization problems, require the implementation of a reflection operator over a target state. Commonly, such reflections are approximately implemented using phase estimation. Here we use a linear combination of unitaries and a version of amplitude amplification to approximate reflection operators over eigenvectors of unitary operators using exponentially less ancillary qubits in terms of a precision parameter. The gate complexity of our method is also comparable to that of the phase estimation approach in a certain limit of interest. Like phase estimation, our method requires the implementation of controlled unitary operations. We then extend our results to the Hamiltonian case where the target state is an eigenvector of a Hamiltonian whose matrix elements can be queried. Our results are useful in that they reduce the resources required by various quantum algorithms in the literature. Our improvements also rely on an efficient quantum algorithm to prepare a quantum state with Gaussian-like amplitudes that may be of independent interest. We also provide a lower bound on the query complexity of implementing approximate reflection operators on a quantum computer.
Deterministic exact inversion of an arbitrary d-dimensional unitary requires {Θ(d2)} coherent forward calls in the worst case. We ask how this cost changes for Hamiltonian evolution U(x)=exp(i∑jxjHj) when the generators are known but the parameters are hidden. For one-parameter families with a fixed eigenbasis, we show that additive relations among the distinct eigenvalues determine the optimal query number exactly, and we construct the corresponding inversion protocol. For general families, we prove that repeated symmetry sectors do not affect the exact query complexity and give an automatic construction for combining inverses from inequivalent active sectors. We also give a sufficient phase-alignment condition under which family-specific structure can reduce the query number. These results establish structure-dependent bounds for reversing the unknown dynamics arising in Tavis-Cummings out-of-time-order correlator protocols, collective-spin echo verification, and passive multimode links, without requiring prior knowledge or explicit estimation of the underlying coupling strengths.
In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.