Algorithms · Statistical inference · spiked tensor
Tensor principal component analysis for the spiked tensor model
In the spiked tensor model, an unknown signal vector v_sig in R^N of magnitude √N is hidden inside a p-th order tensor T0 = λ v_sig^⊗p + G, where G is noise whose entries are chosen independently from a Gaussian distribution of zero mean and unit variance and λ is a scalar representing a signal-to-noise ratio; the task called recovery is to infer v_sig to some accuracy given T0, and the simpler task called detection is to distinguish the case λ = 0 from λ = λ̄ for some λ̄ > 0, again just given T0. The paper treats the symmetrized and non-symmetrized cases as reducible to each other, and says that for odd p it is convenient in the analysis not to symmetrize T0 and to take complex G. Recovery is information-theoretically possible for λ much larger than N^((1-p)/2), but no polynomial-time algorithm is known that achieves that performance; the two best known algorithms are spectral and sum-of-squares, and for even p the spectral method works for λ much larger than N^(-p/4), with a variant conjectured to perform similarly for odd p. The regime this record is about is the hard one at and below that spectral threshold: write λ = α N^(-p/4), and the question is what recovery costs as α shrinks.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial (quartic)
- Primary source on the speedupStated by the primary source: "The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space."
- Reported costBoth sides of the comparison are indexed by nbos, and the object whose size sets the cost is D(N, nbos), the dimension of the symmetric subspace of nbos qudits of dimension N, which the paper approximates by N^nbos / nbos! for N much greater than nbos; Emax is its high-probability bound on the largest eigenvalue of the noise Hamiltonian H(G) and E0 the signal energy scale, with the algorithms analysed for E0 at least (1 + c) Emax. Classically, one iteration of the power method on H(T0) takes time Õ(D(N, nbos)) in space Õ(D(N, nbos)), and O(log(D(N, nbos)) / log(E0/Emax)) iterations suffice for detection and recovery, so the paper's total is Õ(D(N, nbos))O(1 / log(E0/Emax)) with space exponential in nbos. Theorem 6 bounds the quantum algorithm's expected runtime by poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4); the intermediate versions of the same algorithm cost D(N, nbos) and D(N, nbos)^(1/2) times that same poly factor, with plain phase estimation and with amplitude amplification respectively. The polynomial-space claim is not part of theorem 6: it is section 5.2's statement that, in contrast to the classical algorithms above, all these quantum algorithms take only polynomial space. The quartic is a statement about exponents in a stated limit — the log of the quantum runtime divided by the log of the classical runtime approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ, that is, at fixed α. The regime is Assumption 1 together with the paper's standing assumption on λ: nbos = O(N^θ) for a p-dependent constant θ > 0 chosen sufficiently small, λ = Ω(N^(-θ′)) for a p-dependent constant θ′ > p/4, and λ = O(N^(-p/4)) — above that last bound the paper says simple spectral methods already succeed. Below the threshold the price is paid in nbos, which the paper states increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)) while the runtime increases exponentially. The Zoo's own form for the classical cost, exponential in α^(-1), is the one the paper gives for the sum-of-squares sequence and for the Kikuchi-hierarchy spectral algorithms of Wein, El Alaoui and Moore, not for Hastings's own nbos ladder, whose exponent 4/(p-2) equals 1 only at p = 6.
- Papers3
A part this method uses, worked through
This page says amplitude amplification
— here is a concrete, runnable instance of it.
Grover's algorithm finds |101⟩
3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.
Where it ends up
- 10195%
- 0001%
- 1101%
- 0011%
- 4 more outcomes3%
Measuring gives 101, the marked state, with high probability.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioIn the spiked tensor model, an unknown signal vector v_sig in R^N of magnitude √N is hidden inside a p-th order tensor T0 = λ v_sig^⊗p + G, where G is noise whose entries are chosen independently from a Gaussian distribution of zero mean and unit variance and λ is a scalar representing a signal-to-noise ratio; the task called recovery is to infer v_sig to some accuracy given T0, and the simpler task called detection is to distinguish the case λ = 0 from λ = λ̄ for some λ̄ > 0, again just given T0. The paper treats the symmetrized and non-symmetrized cases as reducible to each other, and says that for odd p it is convenient in the analysis not to symmetrize T0 and to take complex G. Recovery is information-theoretically possible for λ much larger than N^((1-p)/2), but no polynomial-time algorithm is known that achieves that performance; the two best known algorithms are spectral and sum-of-squares, and for even p the spectral method works for λ much larger than N^(-p/4), with a variant conjectured to perform similarly for odd p. The regime this record is about is the hard one at and below that spectral threshold: write λ = α N^(-p/4), and the question is what recovery costs as α shrinks. Hastings turns the spiked-tensor problem into a many-body eigenvector problem. The tensor T0 defines a Hamiltonian H(T0) on some number nbos of qudits of dimension N, restricted to their symmetric subspace so that the nbos qudits behave as bosons, and mean-field theory suggests that for large nbos the leading eigenvector can be approximated by a product state; the paper proves that for this statistical model the mean-field approximation becomes accurate with high probability at much smaller nbos than the bounds for arbitrary pairwise Hamiltonians would require. It is careful about what that buys. It does not prove that the nbos-fold tensor product of the single-particle state built from v_sig approximates the leading eigenvector, only that it is a good approximation to some state in an eigenspace with large eigenvalue, and section 5 opens by emphasizing that it is not necessary to find the leading eigenvector itself. Theorems 3 and 5, for even and odd p, then show that any state whose energy exceeds (1 + c′) Emax has, with high probability, a single-particle density matrix whose normalized overlap with v_sig is at least (c′ − o(1)) Emax/E0, so recovery reduces to producing some vector in the eigenspace above the cut. Classically that is the power method on a vector of dimension D(N, nbos), the dimension of the symmetric subspace, which the paper approximates by N^nbos / nbos! and which costs time and space of that order. The quantum algorithm instead phase estimates with H(T0) on a prepared input state and keeps the run only when the eigenvalue lands above the cut: a random input succeeds with probability very close to 1/D(N, nbos), so the plain version buys nothing over classical, amplitude amplification takes the expected time down to D(N, nbos)^(1/2), and a second idea — using the tensor T0 itself to prepare an input state with larger projection onto the target eigenvector — gives a further quadratic speedup, D(N, nbos)^(1/4), which is the quartic. Raising nbos buys recovery at smaller λ at exponentially higher cost, and the abstract sums up the classical side as algorithms with an improved threshold for recovery that work for both even and odd order tensors.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Hastings turns the spiked-tensor problem into a many-body eigenvector problem. The tensor T0 defines a Hamiltonian H(T0) on some number nbos of qudits of dimension N, restricted to their symmetric subspace so that the nbos qudits behave as bosons, and mean-field theory suggests that for large nbos the leading eigenvector can be approximated by a product state; the paper proves that for this statistical model the mean-field approximation becomes accurate with high probability at much smaller nbos than the bounds for arbitrary pairwise Hamiltonians would require. It is careful about what that buys. It does not prove that the nbos-fold tensor product of the single-particle state built from v_sig approximates the leading eigenvector, only that it is a good approximation to some state in an eigenspace with large eigenvalue, and section 5 opens by emphasizing that it is not necessary to find the leading eigenvector itself. Theorems 3 and 5, for even and odd p, then show that any state whose energy exceeds (1 + c′) Emax has, with high probability, a single-particle density matrix whose normalized overlap with v_sig is at least (c′ − o(1)) Emax/E0, so recovery reduces to producing some vector in the eigenspace above the cut. Classically that is the power method on a vector of dimension D(N, nbos), the dimension of the symmetric subspace, which the paper approximates by N^nbos / nbos! and which costs time and space of that order. The quantum algorithm instead phase estimates with H(T0) on a prepared input state and keeps the run only when the eigenvalue lands above the cut: a random input succeeds with probability very close to 1/D(N, nbos), so the plain version buys nothing over classical, amplitude amplification takes the expected time down to D(N, nbos)^(1/2), and a second idea — using the tensor T0 itself to prepare an input state with larger projection onto the target eigenvector — gives a further quadratic speedup, D(N, nbos)^(1/4), which is the quartic. Raising nbos buys recovery at smaller λ at exponentially higher cost, and the abstract sums up the classical side as algorithms with an improved threshold for recovery that work for both even and odd order tensors. This record's speedup class, "Polynomial (quartic)", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Stated by the primary source: "The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space.". Reported cost: Both sides of the comparison are indexed by nbos, and the object whose size sets the cost is D(N, nbos), the dimension of the symmetric subspace of nbos qudits of dimension N, which the paper approximates by N^nbos / nbos! for N much greater than nbos; Emax is its high-probability bound on the largest eigenvalue of the noise Hamiltonian H(G) and E0 the signal energy scale, with the algorithms analysed for E0 at least (1 + c) Emax. Classically, one iteration of the power method on H(T0) takes time Õ(D(N, nbos)) in space Õ(D(N, nbos)), and O(log(D(N, nbos)) / log(E0/Emax)) iterations suffice for detection and recovery, so the paper's total is Õ(D(N, nbos))O(1 / log(E0/Emax)) with space exponential in nbos. Theorem 6 bounds the quantum algorithm's expected runtime by poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4); the intermediate versions of the same algorithm cost D(N, nbos) and D(N, nbos)^(1/2) times that same poly factor, with plain phase estimation and with amplitude amplification respectively. The polynomial-space claim is not part of theorem 6: it is section 5.2's statement that, in contrast to the classical algorithms above, all these quantum algorithms take only polynomial space. The quartic is a statement about exponents in a stated limit — the log of the quantum runtime divided by the log of the classical runtime approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ, that is, at fixed α. The regime is Assumption 1 together with the paper's standing assumption on λ: nbos = O(N^θ) for a p-dependent constant θ > 0 chosen sufficiently small, λ = Ω(N^(-θ′)) for a p-dependent constant θ′ > p/4, and λ = O(N^(-p/4)) — above that last bound the paper says simple spectral methods already succeed. Below the threshold the price is paid in nbos, which the paper states increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)) while the runtime increases exponentially. The Zoo's own form for the classical cost, exponential in α^(-1), is the one the paper gives for the sum-of-squares sequence and for the Kikuchi-hierarchy spectral algorithms of Wein, El Alaoui and Moore, not for Hastings's own nbos ladder, whose exponent 4/(p-2) equals 1 only at p = 6..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial (quartic)
- Primary source on the speedup
- Stated by the primary source: "The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space."
- Reported cost
- Both sides of the comparison are indexed by nbos, and the object whose size sets the cost is D(N, nbos), the dimension of the symmetric subspace of nbos qudits of dimension N, which the paper approximates by N^nbos / nbos! for N much greater than nbos; Emax is its high-probability bound on the largest eigenvalue of the noise Hamiltonian H(G) and E0 the signal energy scale, with the algorithms analysed for E0 at least (1 + c) Emax. Classically, one iteration of the power method on H(T0) takes time Õ(D(N, nbos)) in space Õ(D(N, nbos)), and O(log(D(N, nbos)) / log(E0/Emax)) iterations suffice for detection and recovery, so the paper's total is Õ(D(N, nbos))O(1 / log(E0/Emax)) with space exponential in nbos. Theorem 6 bounds the quantum algorithm's expected runtime by poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4); the intermediate versions of the same algorithm cost D(N, nbos) and D(N, nbos)^(1/2) times that same poly factor, with plain phase estimation and with amplitude amplification respectively. The polynomial-space claim is not part of theorem 6: it is section 5.2's statement that, in contrast to the classical algorithms above, all these quantum algorithms take only polynomial space. The quartic is a statement about exponents in a stated limit — the log of the quantum runtime divided by the log of the classical runtime approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ, that is, at fixed α. The regime is Assumption 1 together with the paper's standing assumption on λ: nbos = O(N^θ) for a p-dependent constant θ > 0 chosen sufficiently small, λ = Ω(N^(-θ′)) for a p-dependent constant θ′ > p/4, and λ = O(N^(-p/4)) — above that last bound the paper says simple spectral methods already succeed. Below the threshold the price is paid in nbos, which the paper states increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)) while the runtime increases exponentially. The Zoo's own form for the classical cost, exponential in α^(-1), is the one the paper gives for the sum-of-squares sequence and for the Kikuchi-hierarchy spectral algorithms of Wein, El Alaoui and Moore, not for Hastings's own nbos ladder, whose exponent 4/(p-2) equals 1 only at p = 6.
- Speedup class
- Polynomial (quartic) (checked against the record's own primary paper, which states it)
- Complexity basis
- Abstract of arXiv:1907.12724, read off the arXiv abs page: "The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space." What "quartic" is defined to mean is in section 1.2 of the same paper: "The runtime bound for the fastest quantum algorithm is in theorem 6. This theorem gives a quartic improvement in the runtime compared to the fastest classical spectral algorithm; more precisely the log of the runtime with the quantum algorithm divided by the log of the runtime of the classical algorithm approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ." Theorem 6: "Let Assumption 1 hold. For E0 ≥ Emax · (1 + c), for any c > 0, with high probability, the expected runtime of the algorithm is at most poly(N, nbos, 1/(E0 − Emax, log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4)." (The unbalanced bracket after 1/(E0 − Emax is the source's own and is reproduced here as printed rather than repaired; subscripts and superscripts are flattened by pdftotext and restored, and the ε was checked against the ar5iv MathML of the same theorem, which spells that symbol out as epsilon inside the same expression.) Classical side, section 5.1: "The space required is then only Õ(D(N, nbos)). The time required for a single iteration of the power method is Õ(D(N, nbos))", and "So, the time is Õ(D(N, nbos))O(1/ log(E0/Emax))". Polynomial space is claimed in section 5.2, not in theorem 6: "In contrast to the classical algorithms above, all these algorithms take only polynomial space." Intermediate quantum bounds, section 5.2.1: "with high probability the time for phase estimation is poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)), giving an algorithm runtime D(N, nbos) poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε))", and "applying amplitude amplification, with high probability the algorithm succeeds in expected time D(N, nbos)^(1/2) poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε))". Regime, Assumption 1 in section 1.1: "We assume that nbos = O(N^θ) for some p-dependent constant θ > 0 chosen sufficiently small. We will also assume that λ is Ω(N^(-θ′)) for some p-dependent constant θ′ > p/4.", followed by "Finally, we assume that λ = O(N^(-p/4)). Remark: there is of course no reason to consider λ larger than this since simple spectral methods succeed if λ is ω(N^(-p/4))". Cost of dropping below the threshold, section 1: "the required nbos increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)), but the runtime increases exponentially." The exponential-in-α^(-1) form belongs to different algorithms, same section: "The sum-of-squares method [4, 5] for this problem gives rise to a sequence of algorithms [6, 7], in which one can recover at λ smaller than N^(-p/4) at the cost of runtime and space increasing exponentially in polylog(N)N^(-p/4)/λ. In Ref. [1], a sequence of spectral algorithms with similar performance was shown." Symmetric-subspace dimension, section 3.1: "For N ≫ nbos, we can approximate D(N, nbos) ≈ N^nbos/nbos!". Recovery guarantee, theorem 3 (even p) and the word-for-word identical theorem 5 (odd p): "Given any vector Ψ such that ⟨Ψ|H(T0)|Ψ⟩ ≥ (1 + c′)Emax for any scalar c′ > 0, then with high probability the corresponding single particle density matrix ρ1 obeys ⟨vsig|ρ1|vsig⟩ / N ≥ (c′ − o(1)) Emax/E0." The Zoo entry "Tensor Principal Component Analysis" does its own arithmetic on the same quantities: "Consider λ = α N^(-p/4). The best classical algorithms succeed when α ≫ 1 and have time and space complexity that scale exponentially in α^(-1). The quantum algorithm of [424] solves this problem in polynomial space and with runtime scaling quartically better in α^(-1) than the classical spectral algorithm."
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Statistical inference · spiked tensor with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Tensor principal component analysis for the spiked tensor model
PROBLEM: In the spiked tensor model, an unknown signal vector v_sig in R^N of magnitude √N is hidden inside a p-th order tensor T0 = λ v_sig^⊗p + G, where G is noise whose entries are chosen independently from a Gaussian distribution of zero mean and unit variance and λ is a scalar representing a signal-to-noise ratio; the task called recovery is to infer v_sig to some accuracy given T0, and the simpler task called detection is to distinguish the case λ = 0 from λ = λ̄ for some λ̄ > 0, again just given T0. The paper treats the symmetrized and non-symmetrized cases as reducible to each other, and says that for odd p it is convenient in the analysis not to symmetrize T0 and to take complex G. Recovery is information-theoretically possible for λ much larger than N^((1-p)/2), but no polynomial-time algorithm is known that achieves that performance; the two best known algorithms are spectral and sum-of-squares, and for even p the spectral method works for λ much larger than N^(-p/4), with a variant conjectured to perform similarly for odd p. The regime this record is about is the hard one at and below that spectral threshold: write λ = α N^(-p/4), and the question is what recovery costs as α shrinks.
IDEA: Hastings turns the spiked-tensor problem into a many-body eigenvector problem. The tensor T0 defines a Hamiltonian H(T0) on some number nbos of qudits of dimension N, restricted to their symmetric subspace so that the nbos qudits behave as bosons, and mean-field theory suggests that for large nbos the leading eigenvector can be approximated by a product state; the paper proves that for this statistical model the mean-field approximation becomes accurate with high probability at much smaller nbos than the bounds for arbitrary pairwise Hamiltonians would require. It is careful about what that buys. It does not prove that the nbos-fold tensor product of the single-particle state built from v_sig approximates the leading eigenvector, only that it is a good approximation to some state in an eigenspace with large eigenvalue, and section 5 opens by emphasizing that it is not necessary to find the leading eigenvector itself. Theorems 3 and 5, for even and odd p, then show that any state whose energy exceeds (1 + c′) Emax has, with high probability, a single-particle density matrix whose normalized overlap with v_sig is at least (c′ − o(1)) Emax/E0, so recovery reduces to producing some vector in the eigenspace above the cut. Classically that is the power method on a vector of dimension D(N, nbos), the dimension of the symmetric subspace, which the paper approximates by N^nbos / nbos! and which costs time and space of that order. The quantum algorithm instead phase estimates with H(T0) on a prepared input state and keeps the run only when the eigenvalue lands above the cut: a random input succeeds with probability very close to 1/D(N, nbos), so the plain version buys nothing over classical, amplitude amplification takes the expected time down to D(N, nbos)^(1/2), and a second idea — using the tensor T0 itself to prepare an input state with larger projection onto the target eigenvector — gives a further quadratic speedup, D(N, nbos)^(1/4), which is the quartic. Raising nbos buys recovery at smaller λ at exponentially higher cost, and the abstract sums up the classical side as algorithms with an improved threshold for recovery that work for both even and odd order tensors.
REPORTED COST: Both sides of the comparison are indexed by nbos, and the object whose size sets the cost is D(N, nbos), the dimension of the symmetric subspace of nbos qudits of dimension N, which the paper approximates by N^nbos / nbos! for N much greater than nbos; Emax is its high-probability bound on the largest eigenvalue of the noise Hamiltonian H(G) and E0 the signal energy scale, with the algorithms analysed for E0 at least (1 + c) Emax. Classically, one iteration of the power method on H(T0) takes time Õ(D(N, nbos)) in space Õ(D(N, nbos)), and O(log(D(N, nbos)) / log(E0/Emax)) iterations suffice for detection and recovery, so the paper's total is Õ(D(N, nbos))O(1 / log(E0/Emax)) with space exponential in nbos. Theorem 6 bounds the quantum algorithm's expected runtime by poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4); the intermediate versions of the same algorithm cost D(N, nbos) and D(N, nbos)^(1/2) times that same poly factor, with plain phase estimation and with amplitude amplification respectively. The polynomial-space claim is not part of theorem 6: it is section 5.2's statement that, in contrast to the classical algorithms above, all these quantum algorithms take only polynomial space. The quartic is a statement about exponents in a stated limit — the log of the quantum runtime divided by the log of the classical runtime approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ, that is, at fixed α. The regime is Assumption 1 together with the paper's standing assumption on λ: nbos = O(N^θ) for a p-dependent constant θ > 0 chosen sufficiently small, λ = Ω(N^(-θ′)) for a p-dependent constant θ′ > p/4, and λ = O(N^(-p/4)) — above that last bound the paper says simple spectral methods already succeed. Below the threshold the price is paid in nbos, which the paper states increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)) while the runtime increases exponentially. The Zoo's own form for the classical cost, exponential in α^(-1), is the one the paper gives for the sum-of-squares sequence and for the Kikuchi-hierarchy spectral algorithms of Wein, El Alaoui and Moore, not for Hastings's own nbos ladder, whose exponent 4/(p-2) equals 1 only at p = 6.
BASIS: Abstract of arXiv:1907.12724, read off the arXiv abs page: "The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space." What "quartic" is defined to mean is in section 1.2 of the same paper: "The runtime bound for the fastest quantum algorithm is in theorem 6. This theorem gives a quartic improvement in the runtime compared to the fastest classical spectral algorithm; more precisely the log of the runtime with the quantum algorithm divided by the log of the runtime of the classical algorithm approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ." Theorem 6: "Let Assumption 1 hold. For E0 ≥ Emax · (1 + c), for any c > 0, with high probability, the expected runtime of the algorithm is at most poly(N, nbos, 1/(E0 − Emax, log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4)." (The unbalanced bracket after 1/(E0 − Emax is the source's own and is reproduced here as printed rather than repaired; subscripts and superscripts are flattened by pdftotext and restored, and the ε was checked against the ar5iv MathML of the same theorem, which spells that symbol out as epsilon inside the same expression.) Classical side, section 5.1: "The space required is then only Õ(D(N, nbos)). The time required for a single iteration of the power method is Õ(D(N, nbos))", and "So, the time is Õ(D(N, nbos))O(1/ log(E0/Emax))". Polynomial space is claimed in section 5.2, not in theorem 6: "In contrast to the classical algorithms above, all these algorithms take only polynomial space." Intermediate quantum bounds, section 5.2.1: "with high probability the time for phase estimation is poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)), giving an algorithm runtime D(N, nbos) poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε))", and "applying amplitude amplification, with high probability the algorithm succeeds in expected time D(N, nbos)^(1/2) poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε))". Regime, Assumption 1 in section 1.1: "We assume that nbos = O(N^θ) for some p-dependent constant θ > 0 chosen sufficiently small. We will also assume that λ is Ω(N^(-θ′)) for some p-dependent constant θ′ > p/4.", followed by "Finally, we assume that λ = O(N^(-p/4)). Remark: there is of course no reason to consider λ larger than this since simple spectral methods succeed if λ is ω(N^(-p/4))". Cost of dropping below the threshold, section 1: "the required nbos increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)), but the runtime increases exponentially." The exponential-in-α^(-1) form belongs to different algorithms, same section: "The sum-of-squares method [4, 5] for this problem gives rise to a sequence of algorithms [6, 7], in which one can recover at λ smaller than N^(-p/4) at the cost of runtime and space increasing exponentially in polylog(N)N^(-p/4)/λ. In Ref. [1], a sequence of spectral algorithms with similar performance was shown." Symmetric-subspace dimension, section 3.1: "For N ≫ nbos, we can approximate D(N, nbos) ≈ N^nbos/nbos!". Recovery guarantee, theorem 3 (even p) and the word-for-word identical theorem 5 (odd p): "Given any vector Ψ such that ⟨Ψ|H(T0)|Ψ⟩ ≥ (1 + c′)Emax for any scalar c′ > 0, then with high probability the corresponding single particle density matrix ρ1 obeys ⟨vsig|ρ1|vsig⟩ / N ≥ (c′ − o(1)) Emax/E0." The Zoo entry "Tensor Principal Component Analysis" does its own arithmetic on the same quantities: "Consider λ = α N^(-p/4). The best classical algorithms succeed when α ≫ 1 and have time and space complexity that scale exponentially in α^(-1). The quantum algorithm of [424] solves this problem in polynomial space and with runtime scaling quartically better in α^(-1) than the classical spectral algorithm."
PRIMARY SOURCE: M. B. Hastings (2019), Classical and Quantum Algorithms for Tensor Principal Component Analysis — https://arxiv.org/abs/1907.12724
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Quantum phase estimation
Algorithms
- Amplitude amplification
Algorithms
- Approximating the top eigenvector of a Hermitian matrix
Algorithms
- Estimating log-determinants and other spectral sums
Algorithms
References
- Classical and Quantum Algorithms for Tensor Principal Component Analysis
M. B. Hastings · 2019
Primary source. It gives the spectral algorithm, the mean-field Hamiltonian H(T0) that encodes the tensor, recovery guarantees for even p in theorem 3 and for odd p in theorem 5, and the runtime bound in theorem 6 whose exponent is the quartic the Zoo's class quotes. Consult it for what Assumption 1 restricts, for the definition of the quartic as a ratio of logarithms at fixed N^(-p/4)/λ, for the prefactors theorem 6 leaves as poly and exp(O(nbos)), and for section 5's own emphasis that it is not necessary to find the leading eigenvector itself — the paper explicitly declines to prove that the mean-field product state approximates that eigenvector.
- The Kikuchi Hierarchy and Tensor PCA
Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore · 2019
The classical work Hastings's spectral algorithm is closest to and whose normalization he adopts; his abstract describes his classical algorithms as related to, but slightly different from those presented recently in it, with an improved threshold for recovery and coverage of both even and odd order tensors. His remark that no guarantees were given there for odd p is version-scoped: the April 2019 version's abstract states that its results hold for even-order tensors and conjectures that they also hold for odd-order tensors, while the revision now served at this link states that the results apply to tensor PCA for tensors of all orders, and Hastings did not update the remark. Consult it for the classical side of the runtime-versus-statistical-power tradeoff the quantum bound is measured against — its abstract describes a hierarchy of increasingly powerful algorithms with increasing runtime, based on the Kikuchi Hessian, that matches the performance of sum-of-squares in polynomial time and yields a continuum of subexponential-time algorithms.
- A statistical model for tensor PCA
Andrea Montanari, Emile Richard · 2014
Where the spiked tensor model this record states comes from: Hastings cites it as the paper that introduced this statistical model, which it terms the spiked tensor problem, and as where spectral algorithms for it were first suggested. Its abstract uses information theory to establish necessary and sufficient conditions under which the principal component can be estimated using unbounded computational resources, and then analyses polynomial-time estimation algorithms based on tensor unfolding, power iteration and message passing, showing that unless the signal-to-noise ratio diverges in the system dimensions none of those approaches succeeds. Consult it for the information-theoretic threshold that the algorithmic thresholds quoted here fall short of.