{"id":"c1f6756c-8867-4af0-af52-1381729909d5","arxiv_id":"1908.00719","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"Two quantum algorithms for HOSVD are presented, with polylogarithmic time for preparing the decomposed state, plus a hybrid quantum-classical HOSVD recommendation method.","lead":"This paper proposes two quantum algorithms for higher order singular value decomposition of tensors, plus a hybrid quantum-classical scheme for recommendation systems. If the speedups held, big-data tensor analysis and context-aware recommendations could in principle run exponentially faster on a quantum computer.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's eigenvalue resolvability argument (Eq. 45) is internally inconsistent: with eigenvalues at most ~1/N, the phase estimation step cannot resolve them in polylog time.","rationale":"The reader's REJECT verdict identifies a serious flaw in Algorithm 1's Eq. (45) and the excluded data-structure cost. I agree with the REJECT verdict. The most load-bearing concern is the internal inconsistency in Eq. (45): it is not a matter of an unproven oracle but a contradiction within the stated assumptions. The claimed speedup for Algorithm 1 therefore fails even with free oracle access. The reader's weakest_assumption is valid but secondary; the paper's own Section V admits the low-rank requirement only after the fact. I also note the paper's self-referential limitation: Section V explicitly states 'the matrices have to be low-rank' and 'there is no requirement for the structure of the input tensor' for Algorithm 2, which is a manuscript-internal admission that Algorithm 1 does not achieve the claimed general exponential speedup. These internal admissions, combined with the numeric inconsistency (t = Omega(N) vs t = O(polylog n)), justify a REJECT rather than a CONDITIONAL. A revised version that drops Algorithm 1's speedup claim, restricts it to a proper low-rank regime, or replaces it with Algorithm 2's QSVE-based approach could be reconsidered. No ad hominem is intended; the critique concerns the argument only.","tokens_in":18053,"tokens_out":1709,"duration_ms":15181,"concrete_test":"Re-derive Eq. (45) by substituting lambda_j <= ||A~_k||_F/N = O(1/N). If the resolvability condition tr{A~_r^2/N^2} = Omega(r/t^2) is replaced with the correct bound tr{A~_r^2/N^2} <= r||A~||_F^2/N^2, the conclusion r = O(||A||_max^2 t^2) does not follow; instead one obtains no nontrivial upper bound on r. Then check whether the phase estimation subroutine of Section III-C can resolve eigenvalues of size ~1/N with t = O(polylog n) by simulating e^{-i(A~_k/N)t}; if t << N, the phase differences are < 2pi/t and the eigenvalues are not resolvable, confirming the contradiction.","verdict_should_be":"REJECT","load_bearing_attack":"The central speedup claim for Algorithm 1 rests on Eq. (45) in Section V, which asserts that the number r of resolvable eigenvalues satisfies tr{A~_r^2/N^2} = Omega(r/t^2). But the eigenvalues of A~_k/N are at most ||A~_k||_F/N = O(1/N), where N = n + n^{m-1}. Inserting this bound into Eq. (45) gives r/N^2 = Omega(r/t^2), i.e. t = Omega(N), which contradicts the claimed t = O(polylog n). The error analysis in Eq. (19)-(20) is also separate from the eigenvalue-resolvability condition; the trace bound in Eq. (45) mixes a bound on the simulated eigenvalues with a bound on the rank of the truncation A~_r. This is not merely an unproven assumption but an internal inconsistency: the phase estimation register of size d = O(log(1/eps)) can only read out eigenvalues modulo 2pi, and eigenvalues of size ~1/N require simulation time t ~ N to be resolved, so the O(m^2 polylog n) claim for Algorithm 1 cannot hold as written. The reader's weakest_assumption (pre-existing quantum-accessible data structure) is also legitimate, but the internal inconsistency in Eq. (45) is the more load-bearing flaw: it breaks Algorithm 1's advertised complexity even granting a free oracle.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two quantum algorithms for higher-order singular value decomposition (HOSVD) of an mth-order n-dimensional tensor. Algorithm 1 builds a Hermitian extension of each mode-k unfolding, applies a qPCA-style simulation via a sparse SWAP-like operator, and uses phase estimation to prepare a superposition of tensor singular values and singular vectors. Algorithm 2 instead uses the quantum singular value estimation (QSVE) subroutine of Kerenidis and Prakash on each unfolding matrix. The paper claims O(m^2 polylog n) and O(m^3 polylog n) query complexity for the two algorithms, respectively, and hence an exponential speedup over classical HOSVD's O(m n^{m+1}); it also presents a hybrid quantum-classical recommendation-system algorithm based on HOSVD and SGD. The central claims are the two quantum HOSVD algorithms and their complexity analysis in Sections III-V and the summary in Section VII.","tokens_in":18351,"tokens_out":13713,"duration_ms":141143,"significance":"Quantum tensor algorithms are a timely and underexplored topic, and the paper is one of the first to formulate quantum HOSVD. Algorithm 2's structure around QSVE is natural and, under the standard quantum-accessible data structure assumption, could plausibly yield polylogarithmic query complexity for preparing singular-value/vector superpositions of tensor unfoldings. The hybrid recommendation application is also a reasonable extension of existing quantum recommendation ideas. However, the paper's headline exponential speedup is not established: Algorithm 1's complexity argument contains an internal inconsistency in the eigenvalue-resolvability analysis, and the cost of producing explicit singular matrices/core tensors as well as the preprocessing cost of the data structure are not accounted for. These issues are load-bearing for the main claims, so the contribution as it stands is not sound enough for publication.","major_comments":[{"comment":"The eigenvalue-resolvability argument is internally inconsistent. With the normalization ||A||_F = 1, the Hermitian extension ~A^(k) in Eq. (16) has Frobenius norm sqrt(2), so the simulated Hamiltonian H = ~A^(k)/N has eigenvalues mu_j satisfying sum_j mu_j^2 = ||H||_F^2 = 2/N^2; in particular |mu_j| <= sqrt(2)/N. The condition |mu_j| = Omega(1/t) that the text imposes for phase estimation at simulation time t therefore forces t = Omega(N). Substituting this spectral bound into the lower bound in Eq. (45) gives Omega(r/t^2) <= tr(H_r^2) <= 2/N^2, hence t = Omega(N) unless r = 0. This contradicts the subsequent choice t = O(polylog n) and invalidates the derived rank bound r = O(||A||_max^2 t^2). Consequently the advertised O(m^2 polylog n) complexity of Algorithm 1 does not follow from the stated simulation.","section":"Section V, Eq. (45)"},{"comment":"The claimed complexities O(m^3 n^2 polylog n) and O(m^4 n^2 polylog n) for obtaining the singular matrices and core tensor are not derived and appear inconsistent with the algorithm as written. Step 4 obtains each U^(k) by measurement and amplitude amplification in T_U = O(n^{3/2}) per mode, giving O(m n^{3/2}) in total, while Step 5 costs O(m sqrt(n)/epsilon) by Eq. (35). No m^3 n^2 or m^4 n^2 factor appears in these ingredients. If the intention is to output the complete classical matrices and tensor, a readout lower bound of Omega(n^2) or Omega(n^m) applies and is not discussed. The summary in Section VII therefore overstates what the algorithm is shown to deliver.","section":"Section V (final paragraph) and Sections III.D-III.E"},{"comment":"The exponential-speedup comparison excludes the cost of constructing the quantum-accessible data structure. Theorem 1 and Lemma 3 provide O(polylog(n^m)) state-preparation time only after the tree structure has been built, and building it from the n^m entries requires Omega(n^m) time and memory. Algorithm 1's Step 1 says 'Load A into qRAM', but this preprocessing is never included in the runtime. Since the abstract and Section VII compare against the full classical cost O(m n^{m+1}), the comparison is between a query complexity under a strong input model and an unconditional classical cost. This distinction should be stated explicitly and the speedup claims adjusted accordingly.","section":"Section VII vs. Theorem 1 and Lemma 3"}],"minor_comments":[{"comment":"The text says that projecting onto the u_j part succeeds 'with probability <~u_j|u_j,0> = 1/2'; since |~u_j> = (u_j; +/- v_j)/sqrt(2), the inner product is 1/sqrt(2) and the probability is |<~u_j|u_j,0>|^2 = 1/2. Please correct the displayed value.","section":"Section III.D, after Eq. (29)"},{"comment":"The claimed O(m^3 polylog n) complexity for Algorithm 2 lacks a derivation. The stated ingredients give O(m polylog n) per mode, so a sequential implementation would cost O(m^2 polylog n); either way the extra factor of m needs explanation.","section":"Section V, Algorithm 2 complexity"},{"comment":"In the recommendation application, the cost of preparing the subtensor states |s> after each SGD update is not counted. The factor matrices and core tensor change at every iteration, so the underlying data structure must be updated, but the stated complexity O(K m^2 d polylog d) does not include this.","section":"Section VI, Algorithm 3"},{"comment":"The notation for the column norms of U^(k) is used inconsistently: the state in Eq. (31) includes a factor ||U^(k)_{bullet j_k}||_2 while the surrounding text sometimes treats the columns as unnormalized; please clarify the normalization convention.","section":"Section III.E, Eq. (31)"},{"comment":"There are several typographical and grammatical errors, including 'Base on this algorithm' in Section I and inconsistent spacing in displayed equations; a careful proofreading pass is needed.","section":"General"}],"recommendation":"reject","confidential_remarks":"The flaw in Eq. (45) is central and cannot be repaired by local editing while preserving Algorithm 1's advertised speedup; removing Algorithm 1 or replacing its simulation strategy would be a substantial rewrite. The authors may wish to resubmit a version focused on Algorithm 2 with a precise statement of the input model and output costs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the stress-test is right, and it is the main problem. Algorithm 1's complexity claim is internally inconsistent. Eq. (45) says tr(\\tilde A_r^2/N^2)=Omega(r/t^2), but the eigenvalues of \\tilde A/N are at most O(1/N) under their normalization, so the left side is O(r/N^2). That forces t=Omega(N), contradicting t=O(polylog n). The rank bound r=O(t^2) is vacuous and the claimed O(m^2 polylog n) for Algorithm 1 does not hold as written. This is not a missing assumption; it is a contradiction in their own equations. What is actually here: the paper extends the qRAM tree data structure to tensors, builds a SWAP operator for mode-k unfolding, and offers two routes to HOSVD. Algorithm 2 (QSVE on the conjugate transpose of each unfolding) is a straightforward but legitimate composition of known tools. The hybrid recommendation scheme is a new application of amplitude estimation to gradient inner products, though it shares structure with their earlier t-SVD work. Where it is soft beyond the main flaw: the output model is ambiguous. The exponential speedup is only for preparing a coherent superposition of singular values/vectors; explicit reconstruction costs O(m^3 n^2 polylog n), which is not exponential for m=2 and is only exponential in n for larger m if you ignore the polynomial dependence on n. The oracle assumptions are standard in this literature, so I would not call that a flaw per se, but the paper should state plainly that the classical data structure is the bottleneck. Algorithm 2 is under-specified: error propagation through controlled-mode QSVE and post-selection is not analyzed. The recommendation section assumes efficient preparation of subtensor states without saying how. Who gets value: students wanting a catalog of quantum tensor decomposition subroutines; researchers working on QSVE applications. But nobody should rely on Algorithm 1 until repaired. Recommendation: I would send this to peer review rather than desk reject. The flaws are substantive but identifiable, and Algorithm 2 plus the recommendation scheme could be salvageable. A good referee would send it back for major revision. As it stands, reject.","headline":"Algorithm 1's complexity claim is internally inconsistent, but Algorithm 2 and the recommendation scheme are worth a major-revision review.","tokens_in":698,"tokens_out":738,"would_cite":false,"duration_ms":36889,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12","15A69"],"pacs":["03.67.Ac","03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper presents two quantum algorithms for higher-order singular value decomposition (HOSVD), claiming polylogarithmic runtime and exponential speedup over the classical method.","keywords":["higher-order singular value decomposition","quantum algorithm","tensor decomposition","quantum principal component analysis","quantum singular value estimation","qRAM","recommendation systems","exponential speedup"],"falsifier":"Compare end-to-end runtimes including data-structure construction: if any faithful preparation of the input requires reading all $n^m$ entries, the total time is $\\Omega(n^m)$, so the claimed exponential advantage over $O(m n^{m+1})$ classical HOSVD would not hold as an end-to-end statement. A concrete check would be to instantiate the qRAM data structure for a dense $n\\times n\\times n$ tensor and count the entry-loading operations, or to run Algorithm 2 with the data-structure build cost included and show it saturates the classical time.","tokens_in":17848,"feed_emoji":"⚛️","tokens_out":8046,"duration_ms":67410,"temperature":0.7,"pith_summary":"This paper aims to bring higher-order singular value decomposition (HOSVD), a standard tool for analyzing multidimensional data, into the quantum setting. It presents two quantum algorithms that prepare a superposition state encoding a tensor's singular values and singular vectors. For an $m$th-order $n$-dimensional tensor, the first runs in $O(m^2 \\mathrm{polylog}\\, n)$ and the second in $O(m^3 \\mathrm{polylog}\\, n)$, compared with $O(m n^{m+1})$ for classical HOSVD; the first assumes low-rank unfolding matrices, while the second removes that restriction. If the speedup holds, tensor-based machine learning, recommendation systems, and quantum-chemistry computations could handle far larger datasets than classical algorithms permit. The authors also propose a hybrid quantum-classical HOSVD-based recommendation algorithm.","feed_headline":"Two quantum algorithms decompose tensors in polylog time","feed_subtitle":"Classical HOSVD scales with n^(m+1); the new methods claim exponential speedup.","key_machinery":"The load-bearing object is the Hermitian extension of the mode-$k$ unfolding, $\\tilde A^{(k)}$ (the block matrix with $A^{(k)}$ and $A^{(k)\\dagger}$ off-diagonal), together with a SWAP-like operator $S^{(k)}_{\\tilde A}$ built from the entries of the original tensor. Because $S^{(k)}_{\\tilde A}$ is one-sparse in a larger space, its Hamiltonian simulation is efficient, and qPCA on it reveals the singular values and singular vectors of each unfolding. The alternative algorithm replaces this with the quantum singular value estimation operator $W=(2PP^\\dagger-I)(2QQ^\\dagger-I)$, constructed from the row and column state-preparation isometries $P$ and $Q$; phase estimation on $W$ yields the singular values directly. Both algorithms rely on a quantum-accessible tree data structure (with qRAM access) that prepares the tensor state and row states in polylogarithmic time.","core_discovery":"On the paper's own terms, the central discovery is that HOSVD, previously treated as a classical multilinear-algebra routine, can be implemented quantumly with polylogarithmic scaling in the tensor dimension. Algorithm 1 uses quantum principal component analysis on a Hermitian extension of each mode-$k$ unfolding to estimate tensor singular values and vectors; Algorithm 2 uses quantum singular value estimation on the unfolding matrices directly and works for arbitrary input structure. The claimed complexities for preparing the superposition state are $O(m^2 \\mathrm{polylog}\\, n)$ and $O(m^3 \\mathrm{polylog}\\, n)$, respectively, versus $O(m n^{m+1})$ classically. Reconstructing the singular matrices and core tensor explicitly costs $O(m^3 n^2 \\mathrm{polylog}\\, n)$ and $O(m^4 n^2 \\mathrm{polylog}\\, n)$. In addition, the paper applies the HOSVD model to a hybrid quantum-classical recommendation system, where gradient computations are accelerated by quantum inner-product estimation.","pith_inferences":["The end-to-end speedup is conditional on the quantum-accessible data structure already existing: loading an $n^m$-entry tensor classically costs at least $O(n^m)$ time and memory, which is not counted in the polylogarithmic bounds; if that loading cost is included, the exponential separation over classical HOSVD disappears.","Because the same data-structure oracle underlies most quantum machine-learning speedup claims, the HOSVD result inherits the general open question of whether qRAM can be built and maintained cheaply in practice.","A natural extension, not pursued in the paper, is to adapt the two algorithms to other tensor decompositions such as CP or tensor-train, where the same mode-wise singular-value ideas could apply.","The recommendation-system application suggests a testable small-scale experiment: simulate Algorithm 3 with quantum gradient estimates and compare convergence against classical SGD; the paper does not report numerical results."],"forward_implications":["If correct, HOSVD-based tensor analysis in machine learning, signal processing, and quantum chemistry can be run on large tensors whose classical decomposition cost $O(m n^{m+1})$ would be prohibitive.","Algorithm 2 removes the low-rank requirement on the unfolding matrices, so the method applies to dense, high-rank input tensors once the quantum data structure is available.","The hybrid recommendation algorithm shows a concrete downstream use: gradient updates in tensor completion can be evaluated with polylogarithmic quantum subroutines instead of classical $O(K m d^m)$ computations.","The explicit-output versions of both algorithms, with $O(m^3 n^2 \\mathrm{polylog}\\, n)$ and $O(m^4 n^2 \\mathrm{polylog}\\, n)$ costs, set a benchmark for what full HOSVD reconstruction would cost on a quantum computer."],"supporting_citations":[{"why":"Defines the classical HOSVD that the quantum algorithms extend and provides the $O(m n^{m+1})$ baseline.","marker":"[10]"},{"why":"Supplies the quantum singular value estimation procedure and the tree data structure with quantum access used by Algorithm 2.","marker":"[20]"},{"why":"Provides quantum principal component analysis, the engine of Algorithm 1's eigenvalue estimation.","marker":"[24]"},{"why":"The quantum matrix SVD algorithm whose techniques (Hermitian extension, low-rank simulation) Algorithm 1 builds on.","marker":"[35]"},{"why":"Gives the quantum matrix-multiplication subroutine used to compute the core tensor via tensor-matrix products.","marker":"[37]"},{"why":"Shows that sparse Hamiltonians such as the one-sparse SWAP operator can be simulated efficiently, justifying the matrix-exponentiation step.","marker":"[4]"},{"why":"Introduces quantum random access memory, the model for loading tensor entries efficiently in Algorithm 1.","marker":"[12]"},{"why":"Supplies the phase-estimation algorithm used to read out eigenvalues and singular values in both algorithms.","marker":"[22]"}],"fun_headline_variants":["Quantum HOSVD: tensor decomposition with exponential speedup","Polylog-time tensor SVD via two quantum algorithms","Exponential speedup for tensor analysis with quantum HOSVD","Quantum HOSVD: from n^(m+1) to polylog scaling","Two quantum algorithms for HOSVD with polylog complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exponential speedup assumes a pre-existing quantum-accessible data structure that can supply the $n^m$ tensor entries (or every mode-$k$ row state) in polylogarithmic time; building or updating that structure costs at least $O(n^m)$, and that cost is excluded from the complexity claims.","fun_headline_variants_meta":{"raw":{"variants":["Quantum HOSVD: tensor decomposition with exponential speedup","Polylog-time tensor SVD via two quantum algorithms","Exponential speedup for tensor analysis with quantum HOSVD","Quantum HOSVD: from n^(m+1) to polylog scaling","Two quantum algorithms for HOSVD with polylog complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000267,"raw_usage":{"total_tokens":1556,"prompt_tokens":827,"completion_tokens":729,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":443,"completion_tokens_details":{"reasoning_tokens":640}},"tokens_in":443,"tokens_out":729,"duration_ms":6686,"temperature":1.0,"reasoning_tokens":640,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:37:58.117126+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare end-to-end runtimes including data-structure construction: if any faithful preparation of the input requires reading all $n^m$ entries, the total time is $\\Omega(n^m)$, so the claimed exponential advantage over $O(m n^{m+1})$ classical HOSVD would not hold as an end-to-end statement. A concrete check would be to instantiate the qRAM data structure for a dense $n\\times n\\times n$ tensor and count the entry-loading operations, or to run Algorithm 2 with the data-structure build cost included and show it saturates the classical time.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the classical HOSVD that the quantum algorithms extend and provides the $O(m n^{m+1})$ baseline."},{"cited_title":"Eckart-Young","cited_arxiv_id":null,"evidence_quote":"Supplies the quantum singular value estimation procedure and the tree data structure with quantum access used by Algorithm 2."},{"cited_title":"A fast quantum mechanical algorithm for database search","cited_arxiv_id":null,"evidence_quote":"Provides quantum principal component analysis, the engine of Algorithm 1's eigenvalue estimation."},{"cited_title":"Quantum principal component analysis","cited_arxiv_id":null,"evidence_quote":"The quantum matrix SVD algorithm whose techniques (Hermitian extension, low-rank simulation) Algorithm 1 builds on."},{"cited_title":"A ten- sor higher-order singular value decomposition for inte- grative analysis of DNA microarray data from different studies","cited_arxiv_id":null,"evidence_quote":"Gives the quantum matrix-multiplication subroutine used to compute the core tensor via tensor-matrix products."},{"cited_title":"end for 5.S←A× 1 U(1)† ×2 U(2)† ×3···× m U(m)†","cited_arxiv_id":null,"evidence_quote":"Shows that sparse Hamiltonians such as the one-sparse SWAP operator can be simulated efficiently, justifying the matrix-exponentiation step."},{"cited_title":"Variable time amplitude amplification and quantum algorithms for linear algebra problems","cited_arxiv_id":null,"evidence_quote":"Introduces quantum random access memory, the model for loading tensor entries efficiently in Algorithm 1."},{"cited_title":"Machine learning & artificial intelligence in the quantum domain: a re- view of recent progress","cited_arxiv_id":null,"evidence_quote":"Supplies the phase-estimation algorithm used to read out eigenvalues and singular values in both algorithms."}],"review_version":1}