Skip to content

Fan-Cone Certificates Are Not Hidden-Vertex Invariants

Claim/Theorem

A modular-plus-fan Farkas certificate is not, by itself, an obstruction to ordinary hidden-vertex graph-cut expressibility.

The project graph already contains the decisive counterexample:

  1. [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]] gives a fan-cone separating certificate for a 6-qubit stabilizer cut-rank function.

  2. [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]] gives an explicit four-hidden-bit binary-submodular energy realizing that same function.

The new script docs/project_QEM-QEC/tmp/scripts/route_d_certificate_lift.py reconstructs this phenomenon directly. For the 6-qubit witness it finds an integer certificate with:

  • 2598 upper fans and 2598 lower fans;
  • support 58;
  • modular dot zero;
  • minimum fan dot 0;
  • target dot -2;
  • pairwise Hamming-defect minimum 0.

So the same kind of fan-cone dual certificate can occur on a function that is already known to lie in \langle\Gamma_{\mathrm{sub},2}\rangle.

Consequently, the following candidate lift mechanism is false:

Any fan-cone separating certificate, or any certificate satisfying only modular balance plus fan nonnegativity, is automatically a weighted-polymorphism or multimorphism obstruction for hidden-vertex expressibility.

The obstruction route for f_3 therefore cannot proceed by cone duality alone. It must use a certificate with an additional operation-level structure: a conservative Hamming-nonincreasing multimorphism, or a weighted-polymorphism decomposition into such valid inequalities.

This also checks the opposing constructive side. Non-fan hidden-variable energies can evade fan-cone certificates in principle; the six-qubit threshold-lift energy is already an explicit beyond-fan hidden-vertex realization. Thus a future nonseparable selected-threshold energy for f_3, if found, would not contradict the existence of the current fan certificate.

Dependencies

  • [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]]
  • [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]]
  • [[f3-fan-certificate-passes-necessary-multimorphism-tests-but-not-operation-lift.md]]
  • [[source-all-arity-expressive-power-stops-before-fan-certificate-lift.md]]

Conflicts/Gaps

  • This node does not refute the possibility that the specific f_3 certificate, or a refined certificate derived from it, lifts to a weighted-polymorphism obstruction.
  • It refutes only the generic closure-lift mechanism from fan-cone separation to hidden-vertex nonexpressibility.
  • The six-qubit witness is not the connected size-2 multi-parallel family; it is used here as a calibration example proving that fan certificates are cone-specific unless extra operation-level structure is supplied.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • 10.48550/arXiv.2109.14599
  • local computation: docs/project_QEM-QEC/tmp/certificates/six_qubit_certificate_report.json
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_certificate_lift.py