Polynomial Algorithms for Simultaneous Unitary Similarity and Equivalence

• URL: http://arxiv.org/abs/2511.19439v1
• Date: Sat, 08 Nov 2025 09:24:59 GMT
• Title: Polynomial Algorithms for Simultaneous Unitary Similarity and Equivalence
• Authors: Harikrishna VJ, Vittal Rao, Ramakrishnan K. R,
• Abstract summary: We present an algorithm to solve the Simultaneous Unitary Similarity(S.U.S) problem.<n>The algorithms have a complexity of $O(pn4)$.<n>This work finds application in Quantum Evolution, Quantum gate design and Canonical Simulation.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems [7.587280395664776]
  A quantum linear system (QLS) problem asks for the preparation of a quantum state $|vecyrangle$ proportional to the solution of $Avecy = vecb$.<n>We present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $vecb$.
  arXiv  Detail & Related papers  (2025-10-07T05:28:25Z)
• Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model [5.101318208537081]
  We study sublinear-time algorithms for solving linear systems $Sz = b$, where $S$ is a diagonally dominant matrix.<n>We present randomized algorithms that, for any $u in [n]$, return an estimate $z_u$ of $z*_u$ with additive error.<n>We also prove a matching lower bound, showing that the linear dependence on $S_max$ is optimal.
  arXiv  Detail & Related papers  (2025-09-16T14:13:31Z)
• A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials [0.0]
  We investigate the model $Y=tfrac1sqrt1+sigma2(Pi_* X Q_* + sigma Z)<n>Consider the hypothesis testing problem of distinguishing this model from the case where $X$ and $Y$.<n>Results establish a smooth transition in the effectiveness of low-degree algorithms for this problem.
  arXiv  Detail & Related papers  (2025-04-04T00:32:38Z)
• Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem [4.450536872346658]
  We present a novel algorithm which solves the matrix code equivalence problem in the general case.<n>Our algorithm achieves the same time complexity as Narayanan emphet al. but with a lower space complexity.
  arXiv  Detail & Related papers  (2025-04-01T22:39:31Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Partially Unitary Learning [0.0]
  An optimal mapping between Hilbert spaces $IN$ of $left|psirightrangle$ and $OUT$ of $left|phirightrangle$ is presented. An iterative algorithm for finding the global maximum of this optimization problem is developed.
  arXiv  Detail & Related papers  (2024-05-16T17:13:55Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Non-Convex Compressed Sensing with Training Data [0.0]
  We find the solution of the original problem $Ax = b$ with high probability in the range of a one layer linear neural network with comparatively few assumptions on the matrix $A$. In this paper, we consider an alternative, where instead of suitable initial values we are provided with extra training problems $Ax = B_l$, $l=1, dots, p$ that are related to our compressed sensing problem.
  arXiv  Detail & Related papers  (2021-01-20T20:30:59Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.