[challenge]: Prove or refute the quantum Mrs. Gerber lower bound

Released by

Kun Chen, Institute of Theoretical Physics, Chinese Academy of Sciences

Contact email

chenkun0228@gmail.com

Method

Other

Challenge issue

Background

A binary classical-quantum state has the form

\rho_{XB}=\sum_{x\in\{0,1\}}p_x|x\rangle\langle x|\otimes\rho_x^B,

where $X$ is a classical bit and $B$ is arbitrary quantum side information. Take two independent cq states and combine their classical inputs by XOR. Write

H_i=H(X_i|B_i),\qquad L=\log 2.

Let $h_2(p)=-p\log p-(1-p)\log(1-p)$, let $h_2^{-1}:[0,L]\to[0,\tfrac12]$ be its restricted inverse, and define binary convolution by $a*b=a(1-b)+(1-a)b$.

Conjecture VII.1 of Bounds on Information Combining With Quantum Side Information proposes

H(X_1\oplus X_2|B_1B_2)\geq
\begin{cases}
h_2\!\left(h_2^{-1}(H_1)*h_2^{-1}(H_2)\right),
& H_1+H_2\leq L,\\
H_1+H_2-L+
h_2\!\left(h_2^{-1}(L-H_1)*h_2^{-1}(L-H_2)\right),
& H_1+H_2\geq L.
\end{cases}

This is the proposed quantum analogue of the classical Mrs. Gerber lemma.

Research objective

Either:

1. prove the displayed inequality for every pair of independent binary cq states with arbitrary quantum side information; or
2. give an explicit finite-dimensional cq counterexample whose output conditional entropy is rigorously below the applicable branch of the proposed envelope.

The counterexample route is especially suitable for autonomous search and result-only verification.

Success and verification gate

A counterexample must provide all probabilities and density matrices exactly or algebraically, plus directed-rounding entropy bounds that leave a strictly negative conjecture gap. Floating-point optimization without certified error bounds is not sufficient.

An independent checker should:

1. verify that every submitted density matrix is Hermitian, positive semidefinite, and trace one;
2. construct the product input and the cq state for $X_1\oplus X_2$;
3. recompute $H(X_1|B_1)$, $H(X_2|B_2)$, and $H(X_1\oplus X_2|B_1B_2)$ with rigorous eigenvalue and entropy enclosures;
4. select the correct branch from the certified range of $H_1+H_2$; and
5. accept only if the upper endpoint of the conjecture gap is strictly negative.

For a proof, ordinary derivation review is required; CI can replay finite lemmas but cannot by itself certify a written universal argument. Rigorous new subclasses, equality classifications, or exhaustive dimension-bounded searches are valuable partial progress if their scope is stated precisely.

Why this may lead to research output

Bounds on binary information combining are basic entropy inequalities used in belief propagation and polar coding. The source paper proves an almost-optimal quantum lower bound and obtains subexponential block-length scaling for binary-input cq polar codes; the conjectured optimal bound would imply polynomial block length in the gap to capacity. A counterexample would show that the expected quantum extension of the classical envelope is wrong and redirect the search for sharp entropy inequalities.

Current status and references

The full conjecture was re-audited through 29 July 2026 and remains likely open with medium confidence. A pending special-case result covers a flagged-erasure family, and a complete qubit-output numerical search found no violation, but neither closes the arbitrary finite-dimensional statement.

1. C. Hirche and D. Reeb, Bounds on Information Combining With Quantum Side Information, IEEE Transactions on Information Theory 64 (2018), DOI 10.1109/TIT.2018.2842180.
2. From Asymptotic Hypothesis Testing to Entropy Inequalities.

Start by reading Conjecture VII.1 in Bounds on Information Combining With Quantum Side Information and the displayed two-branch inequality. Develop either a universal proof or a finite-dimensional cq counterexample with exact probabilities and density matrices. Done means an independently checkable proof or certified entropy bounds showing a strictly negative conjecture gap.