Multiqubit orthogonal product bases

• URL: http://arxiv.org/abs/2608.18421v1
• Date: Wed, 19 Aug 2026 01:27:51 GMT
• Title: Multiqubit orthogonal product bases
• Abstract summary: We study complete product bases (OPBs) of an $n$-qubit system via the formal-matrix formalism for multiqubitBs.<n>We prove that two formal matrices are equivalent if and only if their multigraphs are isomorphic, thereby reducing the classification of OPBs to graph isomorphism.
• Score: 4.115763274264731
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study complete orthogonal product bases (OPBs) of an $n$-qubit system via the formal-matrix formalism for multiqubit OPBs. To each OPB formal matrix we associate an edge-colored complete multigraph, and we prove that two formal matrices are equivalent if and only if their multigraphs are isomorphic, thereby reducing the classification of OPBs to graph isomorphism. Via subcube partitions and a lemma of Tarsi, we upper bound the number of variables by $2^n - 1$. We also study lower and upper bounds on the number $a_n$ of equivalence classes of $n$-qubit OPBs, by showing that $\binom{a_{n-1}+1}{2} \le a_n \le B_{2^{n-1}}^n$, where $B_m$ denotes the number of partitions of an $m$-element set. These bounds yield the asymptotic behavior $a_n = 2^{2^{n+o(n)}}$. Finally, we obtain a two-phase algorithm that decides whether two OPB formal matrices are equivalent, together with its correctness proof and complexity analysis. The complexity is exponential in the worst case.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring [0.0]
  We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an emphiterated diffusion process on a finite graph.<n>Our comparison with Shor's algorithm is emphconceptual and model-based.<n>We report complexity in two cost measures: digital steps and diffusion steps.
  arXiv  Detail & Related papers  (2026-01-05T19:45:38Z)
• Polynomial Algorithms for Simultaneous Unitary Similarity and Equivalence [0.0]
  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.
  arXiv  Detail & Related papers  (2025-11-08T09:24:59Z)
• A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field [0.0]
  We prove the RLWE-PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor $n = 2r ps$.<n>We also describe a fast multiplication algorithm in the ring of integers of these real subfields.
  arXiv  Detail & Related papers  (2025-04-07T15:01:48Z)
• 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)
• Scaling of symmetry-restricted quantum circuits [42.803917477133346]
  In this work, we investigate the properties of $mathcalMSU(2N)$, $mathcalM$-invariant subspaces of the special unitary Lie group $SU(2N)$.
  arXiv  Detail & Related papers  (2024-06-14T12:12:15Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Multi-Unitary Complex Hadamard Matrices [0.0]
  We analyze the set of real and complex Hadamard matrices with additional symmetry constrains. Such matrices find several applications in quantum many-body theory, tensor networks and classification of multipartite quantum entanglement.
  arXiv  Detail & Related papers  (2023-05-30T20:11:18Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)

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.