This report gives a lower bound of entanglement cost for antisymmetric states of bipartite d-level systems to be log_2 (d/(d-1)) ebit (for d=3, E_c >= 0.585...). The paper quant-ph/0112131 claims that the value is equal to one ebit for d=3, since all of the eigenvalues of reduced matrix of any pure states living in N times tensor product of antisymmetric space is not greater than 2^(-N) thus the von Neumann entropy is not less than N, but the proof is not true. Hence whether the value is equal to or less than one ebit is not clear at this moment.This report gives a lower bound of entanglement cost for antisymmetric states of bipartite d-level systems to be log_2 (d/(d-1)) ebit (for d=3, E_c >= 0.585...). The paper quant-ph/0112131 claims that the value is equal to one ebit for d=3, since all of the eigenvalues of reduced matrix of any pure states living in N times tensor product of antisymmetric space is not greater than 2^(-N) thus the von Neumann entropy is not less than N, but the proof is not true. Hence whether the value is equal to or less than one ebit is not clear at this moment.

arXiv:quant-ph/0203039Mar 8, 20025 citations

The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces

Markus Weimar

arXiv:1111.0057Journal of Approximation TheoryJun 18, 201210 citations

Equivalent Representations in Symmetrized Tensors

Donald R. Tompkins

Physical Review LettersSep 26, 19661 citation

Intractability results for integration in tensor product spaces

Erich Novak, Friedrich Pillichshammer

We prove lower bounds on the worst-case error of numerical integration in tensor product spaces. The information complexity is the minimal number N of function evaluations that is necessary such that the N -th minimal error is less than a factor ε times the initial error, i.e., the error for N = 0 , where ε belongs to ( 0 , 1 ) . We are interested to which extent the information complexity depends on the number d of variables of the integrands. If the information complexity grows exponentially fast in d , then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem, we present two methods for providing lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function and can be seen as a generalization of the method of decomposable reproducing kernels. The second method, although only applicable for positive quadrature rules, does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. Several applications of both methods are presented.We prove lower bounds on the worst-case error of numerical integration in tensor product spaces. The information complexity is the minimal number N of function evaluations that is necessary such that the N -th minimal error is less than a factor ε times the initial error, i.e., the error for N = 0 , where ε belongs to ( 0 , 1 ) . We are interested to which extent the information complexity depends on the number d of variables of the integrands. If the information complexity grows exponentially fast in d , then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem, we present two methods for providing lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function and can be seen as a generalization of the method of decomposable reproducing kernels. The second method, although only applicable for positive quadrature rules, does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. Several applications of both methods are presented.

Journal of ComplexityOct 16, 20243 citations

Lower and Upper Bounds on the Pseudo-Dimension of Tensor Network Models

Behnoush Khavari, Guillaume Rabusseau

Dec 6, 20213 citations

Quantum Query Complexity of the Hyperoctahedral Group

Ji Ho Bae

We determine the quantum query complexity of oracle identification on the hyperoctahedral group $B_N = \{\pm 1\}^N \rtimes S_N$ with respect to the natural representation: $Q_{LV}(B_N) = 2(N-1)$ for all $N \ge 2$ . This is twice the symmetric-group value $Q_{LV}(S_N) = N-1$ ; the doubling arises from an $\varepsilon$ -parity obstruction that restricts the bottleneck representation $\operatorname{sgn}(σ)$ to even tensor powers. The proof combines a reduction to $S_N$ Kronecker products via Rademacher moment polynomials with the bipartition distance formula $d_T(((N),\varnothing),(α,β)) = 2(N-α_1)-|β|$ in the tensor product graph. A closed-form generating function yields the first-appearance multiplicity $(2N-3)!!$ . We also show $Q_{\mathrm{decomp}}(φ) \le 2\,Q_{\mathrm{signed}}(φ)$ , with equality on $B_2$ , and conjecture a link between the adversary bound and the graph eccentricity.We determine the quantum query complexity of oracle identification on the hyperoctahedral group $B_N = \{\pm 1\}^N \rtimes S_N$ with respect to the natural representation: $Q_{LV}(B_N) = 2(N-1)$ for all $N \ge 2$. This is twice the symmetric-group value $Q_{LV}(S_N) = N-1$; the doubling arises from an $\varepsilon$-parity obstruction that restricts the bottleneck representation $\operatorname{sgn}(σ)$ to even tensor powers. The proof combines a reduction to $S_N$ Kronecker products via Rademacher moment polynomials with the bipartition distance formula $d_T(((N),\varnothing),(α,β)) = 2(N-α_1)-|β|$ in the tensor product graph. A closed-form generating function yields the first-appearance multiplicity $(2N-3)!!$. We also show $Q_{\mathrm{decomp}}(φ) \le 2\,Q_{\mathrm{signed}}(φ)$, with equality on $B_2$, and conjecture a link between the adversary bound and the graph eccentricity.

arXiv:2604.13554Apr 15, 20260 citations

We determine the quantum query complexity of oracle identification on the hyperoctahedral group

B_N = \{\pm 1\}^N \rtimes S_N

with respect to the natural representation:

Q_{LV}(B_N) = 2(N-1)

for all

N \ge 2

. This is twice the symmetric-group value

Q_{LV}(S_N) = N-1

; the doubling arises from an

\varepsilon

-parity obstruction that restricts the bottleneck representation

\operatorname{sgn}(σ)

to even tensor powers. The proof combines a reduction to

S_N

Kronecker products via Rademacher moment polynomials with the bipartition distance formula

d_T(((N),\varnothing),(α,β)) = 2(N-α_1)-|β|

in the tensor product graph. A closed-form generating function yields the first-appearance multiplicity

(2N-3)!!

. We also show

Q_{\mathrm{decomp}}(φ) \le 2\,Q_{\mathrm{signed}}(φ)

, with equality on

B_2

, and conjecture a link between the adversary bound and the graph eccentricity.