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:2511.19439

Polynomial Algorithms for Simultaneous Unitary Similarity and Equivalence

Harikrishna V. J, R. Vittal Rao, K. R. Ramakrishnan

math.RAcs.DSquant-phSubmitted Nov 8, 2025• Announced Nov 11, 2025• 0 citations
arXivHTMLPDF

Abstract

We present an algorithm to solve the Simultaneous Unitary Similarity(S.U.S) problem which is to check if there exists a Similarity transformation determined by a Unitary $U$ s.t $UA_lU^*=B_l$, $l \in \{1,...,p\}$, where $A_l$ and $B_l$ are $nxn$ complex matrices. We observe that the problem is simplest when $U$ is diagonal, where we see that the `paths' in the graph defined by non-zero elements of $A_l$ and $B_l$ determine the solution. Inspired by this we generalize this to the case when $U$ is block-diagonal to identify a form refered to as the `Solution-form' using `paths' determined by non-zero sub-matrices of $A_l,B_l$ which are non-zero multiples of Unitary. When not in Solution form we find an equivalent problem to solve by diagonalizing a Hermitian or a Normal matrix related to the sub-matrices. The problem is solved in a maximum of $n$ steps. The same idea can be extended to solve the Simultaneous Unitary Equivalence (S$.$U$.$Eq) problem where we solve for $U,V$ in $UA_lV^*=B_l$, $A_l,B_l$ being $mxn$ Complex rectangular matrices. Here we work with the 'paths' in the related bi-graph to define the Solution-form. The algorithms have a complexity of $O(pn^4)$. This work finds application in Quantum Evolution, Quantum gate design and Simulation. The salient features of each step of the algorithm can be retained as Canonical features to classify a given collection of complex matrices up to Unitary Similarity.

Comments
14 pages, 2 figures

Related papers

Deciding unitary equivalence between matrix polynomials and sets of bipartite quantum states

Eric Chitambar, Carl A. Miller, Yaoyun Shi

In this brief report, we consider the equivalence between two sets of m + 1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree m matrix polynomials are unitarily equivalent; i.e. UAiV† = Bi for 0 ≤ i ≤ m where U and V are unitary and (Ai, Bi) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices U and V.

Quantum Information and Computation•Sep 1, 2011•0 citations

Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States

Eric Chitambar, Carl A. Miller, Yaoyun Shi

In this brief report, we consider the equivalence between two sets of $m+1$ bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree $m$ matrix polynomials are unitarily equivalent; i.e. $UA_iV^\dagger=B_i$ for $0\leq i\leq m$ where $U$ and $V$ are unitary and $(A_i, B_i)$ are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices $U$ and $V$.

arXiv:1010.1018•Oct 5, 2010•0 citations

Deciding unitary equivalence between matrix polynomials and sets of bipartite quantum states

Eric Chitambar, Carl W. Miller, Yaoyun Shi

In this brief report, we consider the equivalence between two sets of $m+1$ bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree $m$ matrix polynomials are unitarily equivalent; i.e. $UA_iV^\dagger=B_i$ for $0\leq i\leq m$ where $U$ and $V$ are unitary and $(A_i, B_i)$ are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices $U$ and $V$.

Quantum Information and Computation•Sep 1, 2011•0 citations

Local unitary equivalence of quantum states and simultaneous orthogonal equivalence

Naihuan Jing, Min Yang, Hui Zhao

The correspondence between local unitary equivalence of bipartite quantum states and simultaneous orthogonal equivalence is thoroughly investigated and strengthened. It is proved that local unitary equivalence can be studied through simultaneous similarity under projective orthogonal transformations, and four parametrization independent algorithms are proposed to judge when two density matrices on ℂd1 ⊗ ℂd2 are locally unitary equivalent in connection with trace identities, Kronecker pencils, Albert determinants and Smith normal forms.

arXiv:1605.00238•Journal of Mathematical Physics•Jun 1, 2016•10 citations

Quantum Eigenvalue Transformations for Arbitrary Matrices

Xabier Gutiérrez, Lorenzo Laneve, Mikel Sanz

Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an $n$-regular block encoding, namely, a block encoding whose $k$-th power reproduces the $k$-th power of the encoded matrix for every $0 < k < n$. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most $n$ to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an $n$-regular one using only $O(\log n)$ ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function $P(A)$, whose action on each Jordan block involves the derivatives of $P$, and not merely the map $λ\mapsto P(λ)$.

quant-pharXiv:2604.19688•Apr 22, 2026•0 citations

Simultaneous stoquasticity

Jacob Bringewatt, Lucas T. Brady

Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.

arXiv:2202.08863•Physical Review A•Jun 9, 2022•2 citations
We present an algorithm to solve the Simultaneous Unitary Similarity(S.U.S) problem which is to check if there exists a Similarity transformation determined by a Unitary UUU s.t UAlU∗=BlUA_lU^*=B_lUAl​U∗=Bl​, l∈{1,...,p}l \in \{1,...,p\}l∈{1,...,p}, where AlA_lAl​ and BlB_lBl​ are nxnnxnnxn complex matrices. We observe that the problem is simplest when UUU is diagonal, where we see that the paths' in the graph defined by non-zero elements of $A_l$ and $B_l$ determine the solution. Inspired by this we generalize this to the case when $U$ is block-diagonal to identify a form refered to as the Solution-form' using `paths' determined by non-zero sub-matrices of Al,BlA_l,B_lAl​,Bl​ which are non-zero multiples of Unitary. When not in Solution form we find an equivalent problem to solve by diagonalizing a Hermitian or a Normal matrix related to the sub-matrices. The problem is solved in a maximum of nnn steps. The same idea can be extended to solve the Simultaneous Unitary Equivalence (S...U...Eq) problem where we solve for U,VU,VU,V in UAlV∗=BlUA_lV^*=B_lUAl​V∗=Bl​, Al,BlA_l,B_lAl​,Bl​ being mxnmxnmxn Complex rectangular matrices. Here we work with the 'paths' in the related bi-graph to define the Solution-form. The algorithms have a complexity of O(pn4)O(pn^4)O(pn4). This work finds application in Quantum Evolution, Quantum gate design and Simulation. The salient features of each step of the algorithm can be retained as Canonical features to classify a given collection of complex matrices up to Unitary Similarity.
In this brief report, we consider the equivalence between two sets of m + 1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree m matrix polynomials are unitarily equivalent; i.e. UAiV† = Bi for 0 ≤ i ≤ m where U and V are unitary and (Ai, Bi) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices U and V.
In this brief report, we consider the equivalence between two sets of m+1m+1m+1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree mmm matrix polynomials are unitarily equivalent; i.e. UAiV†=BiUA_iV^\dagger=B_iUAi​V†=Bi​ for 0≤i≤m0\leq i\leq m0≤i≤m where UUU and VVV are unitary and (Ai,Bi)(A_i, B_i)(Ai​,Bi​) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices UUU and VVV.
In this brief report, we consider the equivalence between two sets of m+1m+1m+1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree mmm matrix polynomials are unitarily equivalent; i.e. UAiV†=BiUA_iV^\dagger=B_iUAi​V†=Bi​ for 0≤i≤m0\leq i\leq m0≤i≤m where UUU and VVV are unitary and (Ai,Bi)(A_i, B_i)(Ai​,Bi​) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices UUU and VVV.
The correspondence between local unitary equivalence of bipartite quantum states and simultaneous orthogonal equivalence is thoroughly investigated and strengthened. It is proved that local unitary equivalence can be studied through simultaneous similarity under projective orthogonal transformations, and four parametrization independent algorithms are proposed to judge when two density matrices on ℂd1 ⊗ ℂd2 are locally unitary equivalent in connection with trace identities, Kronecker pencils, Albert determinants and Smith normal forms.
Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an nnn-regular block encoding, namely, a block encoding whose kkk-th power reproduces the kkk-th power of the encoded matrix for every 0<k<n0 < k < n0<k<n. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most nnn to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an nnn-regular one using only O(log⁡n)O(\log n)O(logn) ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function P(A)P(A)P(A), whose action on each Jordan block involves the derivatives of PPP, and not merely the map λ↦P(λ)λ\mapsto P(λ)λ↦P(λ).
Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.