Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.17826

How many switches does two-Hamiltonian universality require?

Matas Garbaravičius, Michael M. Wolf

math-phquant-phSubmitted Oct 13, 2026• Announced Oct 14, 2026• 0 citations
arXivHTMLPDF

Abstract

Any pair of sufficiently generic Hamiltonians on $\mathbb{C}^d$ generates the full unitary group, i.e., any $W\in U(d)$ can be synthesized to arbitrary precision by alternating between the two evolutions for suitably chosen durations. For any given pair of Hamiltonians, the minimal number of switches required to cover the entire group is at least $d$ and unbounded in general. Despite this, we show that it scales linearly in $d$ in expectation. Assuming that the two spectra are sufficiently generic, we derive constructive upper bounds on the minimal switching number as a function of the change-of-basis matrix between the two eigenbases. In particular, if this matrix has a column whose entries all have equal moduli, as for a complex Hadamard matrix, then $9d$ switches suffice to reach every unitary. To obtain these results, we construct a short exact representation of any unitary as a product of unitaries that are alternately diagonal in two given bases. All bounds are extended to non-generic spectra and bounded evolution times.

Comments
16 pages

Related papers

On Unitary t-Designs from Relaxed Seeds

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim +1 more

The capacity to randomly pick a unitary across the whole unitary group is a powerful tool across physics and quantum information. A unitary t-design is designed to tackle this challenge in an efficient way, yet constructions to date rely on heavy constraints. In particular, they are composed of ensembles of unitaries which, for technical reasons, must contain inverses and whose entries are algebraic. In this work, we reduce the requirements for generating an ε -approximate unitary t-design. To do so, we first construct a specific n-qubit random quantum circuit composed of a sequence of randomly chosen 2-qubit gates, chosen from a set of unitaries which is approximately universal on U ( 4 ) , yet need not contain unitaries and their inverses nor are in general composed of unitaries whose entries are algebraic; dubbed r e l a x e d seed. We then show that this relaxed seed, when used as a basis for our construction, gives rise to an ε -approximate unitary t-design efficiently, where the depth of our random circuit scales as p o l y ( n , t , l o g ( 1 / ε ) ) , thereby overcoming the two requirements which limited previous constructions. We suspect the result found here is not optimal and can be improved; particularly because the number of gates in the relaxed seeds introduced here grows with n and t. We conjecture that constant sized seeds such as those which are usually present in the literature are sufficient.

arXiv:1911.03704•Entropy•Jan 12, 2020•6 citations

Finding small two-qubit circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•13 citations

Fungible dynamics: There are only two types of entangling multiple-qubit interactions

Michael J. Bremner, Jennifer L. Dodd, Michael A. Nielsen +1 more

What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? It has been shown that all two-body Hamiltonian evolutions can be simulated using any fixed two-body entangling n-qubit Hamiltonian and fast local unitaries. By entangling we mean that every qubit is coupled to every other qubit, if not directly, then indirectly via intermediate qubits. We extend this study to the case where interactions may involve more than two qubits at a time. We find necessary and sufficient conditions for an arbitrary n-qubit Hamiltonian to be dynamically universal, that is, able to simulate any other Hamiltonian acting on n qubits, possibly in an inefficient manner. We prove that an entangling Hamiltonian is dynamically universal if and only if it contains at least one coupling term involving an even number of interacting qubits. For odd entangling Hamiltonians, i.e., Hamiltonians with couplings that involve only an odd number of qubits, we prove that dynamic universality is possible on an encoded set of $n\ensuremath{-}1$ logical qubits. We further prove that an odd entangling Hamiltonian can simulate any other odd Hamiltonian and classify the algebras that such Hamiltonians generate. Thus, our results show that up to local unitary operations, there are only two fundamentally different types of entangling Hamiltonian on n qubits. We also demonstrate that, provided the number of qubits directly coupled by the Hamiltonian is bounded above by a constant, our techniques can be made efficient.

arXiv:quant-ph/0307148•Physical Review A•Jan 23, 2004•27 citations

Universal quantum dynamics from two 2-local Hamiltonians

Charles D. Hill, Henry L. Haselgrove

In this paper, we show that the ability to switch globally between two 2-local Hamiltonians on n qubits is sufficient for achieving universal unitary dynamics on those n qubits. Of the two Hamiltonians used in the construction, one is comprised of nearest-neighbour two-qubit interactions on a one-dimensional chain, the other is comprised of single-qubit interactions. We describe a scheme for choosing the switching times in order to generate arbitrary one- and two-qubit gates on the n qubits. However the switching scheme is inefficient, and we leave as an open problem the question of whether the universality of the Hamiltonians can be exploited in an efficient way.

arXiv:0801.4487•Jan 29, 2008•0 citations

GroupFunctions.jl: computing individual entries of the irreducible representations of the unitary group U(d)

David Amaro-Alcalá, Konrad Szymański

GroupFunctions.jl is a Julia library for computing individual matrix elements of irreducible representations of U(d). These matrix elements, called group functions, can be evaluated symbolically or numerically. For SU(2), they reduce to the Wigner D-functions. The library computes these matrix elements in a carrier-space basis enumerated by Gelfand-Tsetlin patterns. It can also compute entire representation operators, construct input unitaries from parameterisations common in quantum optics, translate Gelfand-Tsetlin patterns into occupation-number kets, and compute the associated Schur functions. Results can be exported in a form compatible with Mathematica.

quant-pharXiv:2607.10867•Jul 14, 2026

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group

Daiki Suruga

Estimating properties of unknown unitary operations is a fundamental task in quantum information science. While full unitary tomography requires a number of samples to the unknown unitary scaling linearly with the dimension (implying exponentially with the number of qubits), estimating specific functions of a unitary can be significantly more efficient. In this paper, we present a unified framework for the sample-efficient estimation of arbitrary square integrable functions $f: \mathbf{U}(d) \to \mathbb{C}$, using only access to the controlled-unitary operation. We first provide a tight characterization of the optimal sample complexity when the accuracy is measured by the averaged bias over the unitary $\mathbf{U}(d)$. We then construct a sample-efficient estimation algorithm that becomes optimal under the Probably Approximately Correct (PAC) learning criterion for various classes of functions. Applications include optimal estimation of matrix elements of irreducible representations, the trace, determinant, and general polynomial functions on $\mathbf{U}(d)$. Our technique generalize the Hadamard test and leverage tools from representation theory, yielding both lower and upper bound on sample complexity.

arXiv:2509.05710•Sep 6, 2025•0 citations
Any pair of sufficiently generic Hamiltonians on Cd\mathbb{C}^dCd generates the full unitary group, i.e., any W∈U(d)W\in U(d)W∈U(d) can be synthesized to arbitrary precision by alternating between the two evolutions for suitably chosen durations. For any given pair of Hamiltonians, the minimal number of switches required to cover the entire group is at least ddd and unbounded in general. Despite this, we show that it scales linearly in ddd in expectation. Assuming that the two spectra are sufficiently generic, we derive constructive upper bounds on the minimal switching number as a function of the change-of-basis matrix between the two eigenbases. In particular, if this matrix has a column whose entries all have equal moduli, as for a complex Hadamard matrix, then 9d9d9d switches suffice to reach every unitary. To obtain these results, we construct a short exact representation of any unitary as a product of unitaries that are alternately diagonal in two given bases. All bounds are extended to non-generic spectra and bounded evolution times.
The capacity to randomly pick a unitary across the whole unitary group is a powerful tool across physics and quantum information. A unitary t-design is designed to tackle this challenge in an efficient way, yet constructions to date rely on heavy constraints. In particular, they are composed of ensembles of unitaries which, for technical reasons, must contain inverses and whose entries are algebraic. In this work, we reduce the requirements for generating an ε -approximate unitary t-design. To do so, we first construct a specific n-qubit random quantum circuit composed of a sequence of randomly chosen 2-qubit gates, chosen from a set of unitaries which is approximately universal on U ( 4 ) , yet need not contain unitaries and their inverses nor are in general composed of unitaries whose entries are algebraic; dubbed r e l a x e d seed. We then show that this relaxed seed, when used as a basis for our construction, gives rise to an ε -approximate unitary t-design efficiently, where the depth of our random circuit scales as p o l y ( n , t , l o g ( 1 / ε ) ) , thereby overcoming the two requirements which limited previous constructions. We suspect the result found here is not optimal and can be improved; particularly because the number of gates in the relaxed seeds introduced here grows with n and t. We conjecture that constant sized seeds such as those which are usually present in the literature are sufficient.
An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.
What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? It has been shown that all two-body Hamiltonian evolutions can be simulated using any fixed two-body entangling n-qubit Hamiltonian and fast local unitaries. By entangling we mean that every qubit is coupled to every other qubit, if not directly, then indirectly via intermediate qubits. We extend this study to the case where interactions may involve more than two qubits at a time. We find necessary and sufficient conditions for an arbitrary n-qubit Hamiltonian to be dynamically universal, that is, able to simulate any other Hamiltonian acting on n qubits, possibly in an inefficient manner. We prove that an entangling Hamiltonian is dynamically universal if and only if it contains at least one coupling term involving an even number of interacting qubits. For odd entangling Hamiltonians, i.e., Hamiltonians with couplings that involve only an odd number of qubits, we prove that dynamic universality is possible on an encoded set of $n\ensuremath{-}1$ logical qubits. We further prove that an odd entangling Hamiltonian can simulate any other odd Hamiltonian and classify the algebras that such Hamiltonians generate. Thus, our results show that up to local unitary operations, there are only two fundamentally different types of entangling Hamiltonian on n qubits. We also demonstrate that, provided the number of qubits directly coupled by the Hamiltonian is bounded above by a constant, our techniques can be made efficient.
In this paper, we show that the ability to switch globally between two 2-local Hamiltonians on n qubits is sufficient for achieving universal unitary dynamics on those n qubits. Of the two Hamiltonians used in the construction, one is comprised of nearest-neighbour two-qubit interactions on a one-dimensional chain, the other is comprised of single-qubit interactions. We describe a scheme for choosing the switching times in order to generate arbitrary one- and two-qubit gates on the n qubits. However the switching scheme is inefficient, and we leave as an open problem the question of whether the universality of the Hamiltonians can be exploited in an efficient way.
GroupFunctions.jl is a Julia library for computing individual matrix elements of irreducible representations of U(d). These matrix elements, called group functions, can be evaluated symbolically or numerically. For SU(2), they reduce to the Wigner D-functions. The library computes these matrix elements in a carrier-space basis enumerated by Gelfand-Tsetlin patterns. It can also compute entire representation operators, construct input unitaries from parameterisations common in quantum optics, translate Gelfand-Tsetlin patterns into occupation-number kets, and compute the associated Schur functions. Results can be exported in a form compatible with Mathematica.
Estimating properties of unknown unitary operations is a fundamental task in quantum information science. While full unitary tomography requires a number of samples to the unknown unitary scaling linearly with the dimension (implying exponentially with the number of qubits), estimating specific functions of a unitary can be significantly more efficient. In this paper, we present a unified framework for the sample-efficient estimation of arbitrary square integrable functions f:U(d)→Cf: \mathbf{U}(d) \to \mathbb{C}f:U(d)→C, using only access to the controlled-unitary operation. We first provide a tight characterization of the optimal sample complexity when the accuracy is measured by the averaged bias over the unitary U(d)\mathbf{U}(d)U(d). We then construct a sample-efficient estimation algorithm that becomes optimal under the Probably Approximately Correct (PAC) learning criterion for various classes of functions. Applications include optimal estimation of matrix elements of irreducible representations, the trace, determinant, and general polynomial functions on U(d)\mathbf{U}(d)U(d). Our technique generalize the Hadamard test and leverage tools from representation theory, yielding both lower and upper bound on sample complexity.