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

Quantum Physics Letters

A Simple Rank Testing Procedure and Complexity Analysis for the Factorization Algorithm

Dhananjay P. Mehendale, Pramod S. Joag

Published Apr 1, 2019• 0 citations
Publisher
DOI
10.18576/qpl/080102

Related papers

Random Stinespring superchannel: converting channel queries into dilation isometry queries

Filippo Girardi, Francesco Anna Mele, Haimeng Zhao +2 more

The recently introduced random purification channel, which converts $n$ copies of an arbitrary mixed quantum state into $n$ copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform $n$ parallel queries of an arbitrary quantum channel into $n$ parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most $r$, the procedure can be tailored to yield a Stinespring environment of dimension $r$. We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ is $Θ(d_A d_B r)$.

quant-pharXiv:2512.20599•Dec 24, 2025•22 citations

Experimental Analysis of the Optimization-Based Factorization Algorithm

Junpei Yamaguchi, Tetsuya Izu, Noboru Kunihiro

Lecture notes in computer science•Jan 1, 2025•0 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600•Aug 4, 2026•10 citations

Rational-Valued, Small-Prime-Based Qubit-Qutrit and Rebit-Retrit Rank-4/Rank-6 Conjectured Hilbert-Schmidt Separability Probability Ratios

Paul B. Slater

We implement a procedure-based on the Wishart-Laguerre distribution-recently outlined by {Ż}yczkowski and Khvedelidze, Rogojin and Abgaryan, for the generation of random (complex or real) $N \times N$ density matrices of rank $k \leq N$ with respect to Hilbert-Schmidt (HS) measure. In the complex case, one commences with a Ginibre matrix $A$ of dimensions $k \times k+ 2 (N-k)$, while for a real scenario, one employs a Ginibre matrix $B$ of dimensions $k \times k+1+ 2 (N-k)$. Then, the $k \times k$ product $A A^{\dagger}$ or $B B^T$ is diagonalized-padded with zeros to size $N \times N$-and rotated, obtaining a random density matrix. Implementing the procedure for rank-4 rebit-retrit states, for 800 million Ginibre-matrix realizations, 6,192,047 were found separable, for a sample probability of .00774006-suggestive of an exact value $\frac{387}{5000} =\frac{3^2 \cdot 43}{2^3 \cdot 5^4}=.0774$. A conjecture for the HS separability probability of rebit-retrit systems of full rank is $\frac{860}{6561} =\frac{2^2 \cdot 5 \cdot 43}{3^8} \approx 0.1310775$ (the two-rebit counterpart has been proven to be $\frac{29}{64}=\frac{29}{2^6}$). Subject to these conjectures, the ratio of the rank-4 to rank-6 probabilities would be $\frac{59049}{1000000}=\frac{3^{10}}{2^6 \cdot 5^6} \approx 0.059049$, with the common factor 43 cancelling. As to the intermediate rank-5 probability, a 2006 theorem of Szarek, Bengtsson and {Ż}ycskowski informs us that it must be one-half the rank-6 probability-itself conjectured to be $\frac{27}{1000} =\frac{3^3}{2^3 \cdot 5^3}$, while for rank 3 or less, the associated probabilities must be 0 by a 2009 result of Ruskai and Werner. We are led to re-examine a 2005 qubit-qutrit analysis of ours, in these regards, and now find evidence for a $\frac{70}{2673}=\frac{2 \cdot 5 \cdot 7}{ 3^5 \cdot 11} \approx 0.0261878$ rank-4 to rank-6 probability ratio.

arXiv:2104.11071•Apr 22, 2021•1 citation

Improving the Success Probability for Shor’s Factorization Algorithm

Guoliang Xu, Daowen Qiu, Xiangfu Zou +1 more

Emergence, complexity and computation•Jan 1, 2018•6 citations

Shor’s Factorization Algorithm

Taylor & Francis eBooks•Mar 11, 2008•0 citations
The recently introduced random purification channel, which converts nnn copies of an arbitrary mixed quantum state into nnn copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform nnn parallel queries of an arbitrary quantum channel into nnn parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most rrr, the procedure can be tailored to yield a Stinespring environment of dimension rrr. We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension dAd_AdA​, output dimension dBd_BdB​, and Choi rank rrr is Θ(dAdBr)Θ(d_A d_B r)Θ(dA​dB​r).
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr⁡(φ(dρ))/d\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/dLφ​(ρ)=tr(φ(dρ))/d, where ρρρ is an unknown ddd-dimensional quantum state and φφφ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ)\mathcal{L}_φ(ρ)Lφ​(ρ) from properties of φφφ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ ⁣(d2εlog⁡2(d)max⁡{1,εlog⁡2(d)}+log⁡2(d)ε2), Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), Θ(εlog2(d)max{1,εlog2(d)}d2​+ε2log2(d)​), and the sample complexity of spectrum estimation is Θ ⁣(d2ε2log⁡2(d)max⁡{1,ε2log⁡2(d)}). Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). Θ(ε2log2(d)max{1,ε2log2(d)}d2​). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
We implement a procedure-based on the Wishart-Laguerre distribution-recently outlined by {Ż}yczkowski and Khvedelidze, Rogojin and Abgaryan, for the generation of random (complex or real) N×NN \times NN×N density matrices of rank k≤Nk \leq Nk≤N with respect to Hilbert-Schmidt (HS) measure. In the complex case, one commences with a Ginibre matrix AAA of dimensions k×k+2(N−k)k \times k+ 2 (N-k)k×k+2(N−k), while for a real scenario, one employs a Ginibre matrix BBB of dimensions k×k+1+2(N−k)k \times k+1+ 2 (N-k)k×k+1+2(N−k). Then, the k×kk \times kk×k product AA†A A^{\dagger}AA† or BBTB B^TBBT is diagonalized-padded with zeros to size N×NN \times NN×N-and rotated, obtaining a random density matrix. Implementing the procedure for rank-4 rebit-retrit states, for 800 million Ginibre-matrix realizations, 6,192,047 were found separable, for a sample probability of .00774006-suggestive of an exact value 3875000=32⋅4323⋅54=.0774\frac{387}{5000} =\frac{3^2 \cdot 43}{2^3 \cdot 5^4}=.07745000387​=23⋅5432⋅43​=.0774. A conjecture for the HS separability probability of rebit-retrit systems of full rank is 8606561=22⋅5⋅4338≈0.1310775\frac{860}{6561} =\frac{2^2 \cdot 5 \cdot 43}{3^8} \approx 0.13107756561860​=3822⋅5⋅43​≈0.1310775 (the two-rebit counterpart has been proven to be 2964=2926\frac{29}{64}=\frac{29}{2^6}6429​=2629​). Subject to these conjectures, the ratio of the rank-4 to rank-6 probabilities would be 590491000000=31026⋅56≈0.059049\frac{59049}{1000000}=\frac{3^{10}}{2^6 \cdot 5^6} \approx 0.059049100000059049​=26⋅56310​≈0.059049, with the common factor 43 cancelling. As to the intermediate rank-5 probability, a 2006 theorem of Szarek, Bengtsson and {Ż}ycskowski informs us that it must be one-half the rank-6 probability-itself conjectured to be 271000=3323⋅53\frac{27}{1000} =\frac{3^3}{2^3 \cdot 5^3}100027​=23⋅5333​, while for rank 3 or less, the associated probabilities must be 0 by a 2009 result of Ruskai and Werner. We are led to re-examine a 2005 qubit-qutrit analysis of ours, in these regards, and now find evidence for a 702673=2⋅5⋅735⋅11≈0.0261878\frac{70}{2673}=\frac{2 \cdot 5 \cdot 7}{ 3^5 \cdot 11} \approx 0.0261878267370​=35⋅112⋅5⋅7​≈0.0261878 rank-4 to rank-6 probability ratio.