Renormalized Density Matrices for Quantum Tensor-Train Sweeps

Quantum algorithms for factorizing large tables and multi-way arrays promise running times that grow only with the logarithm of the data size. A prominent example turns a knowledge graph, a sparse 3-way array of (subject, relation, object) facts, into a quantum state and extracts its dominant low-rank structure exponentially faster than any classical method could. The usual explanation for why such promises fail in practice is the condition number, the ratio of a matrix's largest to smallest singular value. We argue that for one important technique this explanation points at the wrong quantity. That technique, density matrix exponentiation, uses copies of a data-derived quantum state as the "Hamiltonian" that drives a computation. When it is used to extract dominant components, what it actually pays for is how small the retained eigenvalues are after the data has been normalized into a unit-trace state. On noisy, sparse relational data those eigenvalues are tiny, because the low-rank part holds only a small share of the total energy (the sum of squared entries).

The proposal is to restructure quantum tensor factorization as a tensor-train sweep, an algorithm that refits one small "core" of a chained factorization at a time while the others are held fixed in orthonormal form. In that form, each step is a pure projection with condition number exactly one. The density matrix used at each step is then normalized by the energy the current low-rank model captures, rather than by the energy of the whole tensor, and this shrinks the required quantum evolution time and number of state copies by a factor we can measure directly on real graphs. We will build a classical emulator that counts quantum resources exactly, run it on standard knowledge-graph and sparse-tensor benchmarks, and determine whether any regime survives against the strongest classical randomized tensor-train method.

Core Claim

Density matrix exponentiation, introduced in Quantum principal component analysis, applies a tiny SWAP interaction between a target state and a fresh copy of the data state $\rho$ many times. Each application reproduces evolution under $e^{-i\rho\epsilon}$ up to an $O(\epsilon^2)$ error. Accumulating $t/\epsilon$ such steps to reach evolution time $t$ gives total error about $t\epsilon$. Simulating time $t$ to accuracy $\delta$ therefore consumes on the order of $t^2/\delta$ copies of $\rho$.

If $\rho = XX^\dagger/\|X\|_F^2$ for a matricized data tensor $X$ with singular values $\sigma_i$, then $\rho$ has eigenvalues

$$\lambda_i = \frac{\sigma_i^2}{\|X\|_F^2}.$$

Phase estimation must separate the smallest retained eigenvalue $\lambda_R$ from the next one, $\lambda_{R+1}$. That requires $t \gtrsim 1/(\lambda_R-\lambda_{R+1})$. Because the retained eigenvalues sum to at most one, $\lambda_R \le 1/R$ always. When the rank-$R$ part captures only a fraction $f$ of the energy, $\lambda_R$ is smaller still by roughly $1/f$.

This is the cost that the polylogarithmic claims of Quantum Machine Learning Algorithm for Knowledge Graphs leave inside their constant. It is a statement about normalized energy at the truncation threshold, not about the global condition number. Tiny trailing singular values do not affect it, because they are discarded rather than inverted.

In a tensor-train sweep held in orthonormal (canonical) form, the core update is $G_k = P_k^\top X_{(k)}$. Here $P_k$ is the matrix with orthonormal columns formed by the fixed left and right cores, and $X_{(k)}$ is the tensor reshaped around mode $k$. No linear system is inverted. The density matrix of the projected data, $P_k^\top X_{(k)}$, has the same leading singular values as $X$ restricted to the model's subspace, but its normalizer is $\|P_k^\top X_{(k)}\|_F^2 \approx f\|X\|_F^2$. The leading eigenvalues and gaps are therefore inflated by about $1/f$. We expect the required evolution time to drop by $1/f$ and the copy count by $1/f^2$, because copies scale as $t^2$.

The new contributions are this renormalization argument, a sparse way of preparing the projected state, and an honest end-to-end resource accounting that includes reading the cores out.

How This Relates to Prior Work

The closest work is Quantum Machine Learning Algorithm for Knowledge Graphs. It prepares density matrices from knowledge-graph slices using quantum random-access memory (a hypothetical memory that loads classical data into superposition) and projects onto dominant singular subspaces with density matrix exponentiation and phase estimation. It motivates this proposal, since its classical tensor SVD beat ComplEx by 16.53% Hits@10 on YAGO3, so low-rank spectral methods are worth accelerating. It is also our main target: it normalizes by the full tensor energy, uses a Tucker-like rather than tensor-train structure, and does not account for state copies or readout. We keep its encoding and change what gets encoded.

The method we reuse comes from Efficient Leverage Score Sampling for Tensor Train Decomposition. That paper computes exact leverage scores, the per-row importance weights for sampling, directly from canonical tensor-train cores. It reports a 26x per-iteration speedup on NELL-2 with accuracy matching exact alternating least squares to the third or fourth decimal place. We use its exact scores to choose which nonzeros of the sparse tensor are loaded into quantum memory. This plays the role that coordinated row sampling plays in Matrix Product Sketching via Coordinated Sampling, which keeps sketches sparse instead of densifying them. Concretely, we prepare a purification of the projected subproblem from sampled nonzeros, so the memory load grows with the sample count rather than with the size of the densified projected tensor. This is the same reason Tensorized Random Projections is unsuitable here: its projections are compactly stored but mix modes and fill in zeros.

Two lines of work constrain the design. On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number reduces condition-number dependence for structured positive-definite systems through a Cholesky-like factorization. A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems replaces $\kappa$ with an instance-aware quantity and uses right rescaling. Both target matrix inversion. Our point is that a canonical tensor-train sweep has no inversion step at all, so these tools address a cost the sweep does not incur.

Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters also removes $\kappa$ by sampling, but only for 2-D regression and without density matrices. We draw on its spirit: use sampling to move cost from spectral quantities to sample counts. Finally, the case studies on q-means (q-means: A quantum algorithm for unsupervised machine learning) and intrusion-detection PCA (Evaluating the potential of quantum machine learning in cybersecurity: A case-study on PCA-based intrusion detection systems) show that spectral parameters measured on real data are what decide whether speedups survive. We follow that empirical habit.

Research Program

The first piece is analysis. We will bound the copies of $\rho$, the total evolution time, and the number of quantum-memory entries loaded per sweep for two routes:

  • the global-normalization route of Ma et al.;
  • the canonical tensor-train route with leverage-sampled sparse purifications.

Both bounds will be stated in terms of the captured-energy fraction $f$, the retained gap $\lambda_R-\lambda_{R+1}$, the sample count, and the tensor order. We will also bound how sampling error in the sketched purification perturbs the retained subspace.

Each bound will include a readout term. Moving the orthogonality center along the train requires the core as classical numbers, and estimating an $R \times I \times R$ core from measurements costs at least on the order of $R^2 I$ samples, where $I$ is the mode size. That term may well erase the advantage in the logarithm of the dimension. We will report it rather than hide it, and analyze the one setting where it can be avoided: answering individual link-prediction queries as state overlaps without materializing the cores.

The second piece is a classical emulator. It computes each route's exact spectra, normalized eigenvalues, gaps, and resulting resource counts on real tensors, using exact singular value decompositions of the small projected subproblems. Alongside the quantum counts it runs the classical algorithms, so that every comparison is made in the same units: entry reads plus arithmetic operations.

Baselines

The naive reference point is exact classical alternating least squares on the tensor train, together with the classical tensor SVD of Ma et al. Both run on the same tensors, ranks, and stopping rule. They anchor reconstruction fit and link-prediction quality, and any quantum route has to match their accuracy.

The strongest competitor on cost is rTT-ALS from Efficient Leverage Score Sampling for Tensor Train Decomposition. It already samples exactly from canonical cores in $O(\log I)$ time per sample, and it reports a 26x per-iteration speedup over standard alternating least squares on NELL-2 with fit matching to the third or fourth decimal place. We will run its released algorithm with the same ranks, sample budgets swept over the same grid as our sketch, and the same convergence tolerance. Beating it means that, at equal fit, the emulated quantum cost of a full sweep, including state preparation, copies, and readout, falls below rTT-ALS's measured entry reads plus operations on at least one real benchmark and at a realistic rank. Merely showing better asymptotic exponents does not count.

The global-normalization quantum route of Ma et al. is the quantum baseline. Beating it means a measured reduction in evolution time close to the predicted $1/f$ at equal subspace accuracy.

Two ablations isolate our ingredients. The first keeps the canonical sweep but normalizes by the full tensor energy, which tests the renormalization effect alone. The second keeps renormalization but loads the densified projected tensor instead of the leverage-sampled sparse purification, which tests the sparsity piece.

For link-prediction quality we treat KGE-CL from KGE-CL: Contrastive Learning of Knowledge Graph Embeddings as a ceiling. It reports 37.8% MRR on FB15k-237 and 59.1% MRR on YAGO3-10. We do not expect a low-rank tensor train to beat it, and we will say so.

Why not just…?

Why not just run rTT-ALS classically? This is the real threat. On graphs with tens of thousands of entities and ranks in the tens, classical sampling is already fast, and the quantum readout cost may dominate everywhere. The emulator settles the question by reporting both costs in common units across ranks and orders, including the synthetic order-12 and order-25 tensors used in Tensorized Random Projections, where classical sample counts grow. If no crossover appears, we will publish a negative result. That result would still correct the polylogarithmic claim for quantum knowledge-graph factorization.

Why not just precondition the quantum tensor SVD with Cholesky-type factorization or right rescaling? Those methods, from On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number and A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems, shrink the cost of inverting a matrix. Extracting dominant components involves no inversion, and rescaling columns changes the spectrum, so the subspace it recovers is a different factorization. We will test this directly: we rescale the unfoldings, then measure both the change in the normalized retained eigenvalue and the angle between the recovered subspace and the original one.

Why not just use variational quantum SVD? Variational Quantum Singular Value Decomposition avoids deep phase estimation but was shown only on 8×8 and 32×32 matrices. It also needs the data written as a combination of unitaries, which can require exponentially many terms for unstructured sparse data, and it can stall on vanishing gradients. We will run it only on KINSHIP-scale unfoldings as a sanity check. It cannot be resource-compared at FB15k-237 scale.

Proposed Experiments

We will use five real benchmarks: KINSHIP for exact small-scale checks, FB15k-237, WN18RR, YAGO3-10, and NELL-2 from the FROSTT repository with about 77 million nonzeros. We will add the Uber and Enron sparse tensors for order and sparsity variation.

The first decisive check is measuring the captured-energy fraction $f$ and the retained gaps on each graph at ranks 10 to 200. The test is whether the measured ratio of evolution times between the two quantum routes tracks $1/f$. If $f$ is close to one on these graphs, the renormalization effect is small and the core claim fails.

The second check sweeps the leverage-sample budget and tests whether the sparse purification keeps the retained subspace within a set angle while the memory load grows with the sample count rather than with the number of densified entries.

The third check measures end-to-end cost against rTT-ALS at matched reconstruction fit, with and without the readout term, and Hits@10 and MRR against classical tensor SVD on FB15k-237 and YAGO3-10.

No reported result was found on Lacuna for quantum resource counts of any knowledge-graph tensor factorization, so those numbers will be the first of their kind and must be released with the emulator.