Rigorous no-go theorems for heralded linear-optical state generation tasks

Technical Summary: Rigorous No-Go Theorems for Heralded Linear-Optical State Generation

Problem Statement
The generation of entangled photonic quantum states is a fundamental requirement for quantum computing, sensing, and communication. While deterministic generation typically requires strong non-linearities—which are experimentally challenging to implement in optical platforms—linear optics offers an accessible alternative. However, linear optics alone permits only a limited set of deterministic transformations. Consequently, state preparation in photonic systems is often implemented probabilistically using single photons, linear-optical networks, and photon detection.

A critical challenge in this domain is determining whether a specific input state can be transformed into a target state using a given measurement pattern (heralding scheme). This feasibility problem maps to deciding whether a system of polynomial equations possesses a solution. While numerical search methods are commonly used, they cannot definitively prove the non-existence of a solution; a failure to find a solution may simply indicate a limitation of the search algorithm rather than a fundamental impossibility. Furthermore, existing algebraic approaches like Gröbner bases, while capable of finding solutions, are computationally expensive (doubly exponential worst-case complexity) and often "progress-free," requiring full calculation before yielding any result.

Methodology
The authors propose applying the Nullstellensatz Linear Algebra (NulLA) algorithm, a technique from algebraic geometry, to rigorously prove the infeasibility of heralded linear-optical state generation tasks.

1. Mathematical Formulation: The task is cast as a system of polynomial equations. An input state $|\psi_{in}\rangle$ is transformed via an unknown linear matrix $A$ into an output state. By conditioning on a specific heralding pattern (measuring $m$ photons in $M$ ancillary modes), a post-selected state $|\psi_{post}\rangle$ is derived. The requirement that $|\psi_{post}\rangle$ be equivalent to a target state $|\psi_{tar}\rangle$ (up to a non-zero scaling factor $\gamma$) leads to the equation $\gamma G = Q$, where $G$ and $Q$ are homogeneous polynomials representing the heralded and target states, respectively. Equating the coefficients of monomials in these polynomials yields a system of polynomial equations where the variables are the elements of the transformation matrix $A$.

2. The NulLA Algorithm: Instead of solving for $A$, the authors utilize the Weak Nullstellensatz to prove that no solution exists. According to Hilbert's Nullstellensatz, a system of polynomial equations has no solution if and only if there exist polynomials $\beta_i$ such that $\sum \beta_i f_i = 1$. This identity is called a Nullstellensatz certificate. The NulLA algorithm attempts to find such a certificate by incrementally increasing the degree $d$ of the polynomials $\beta_i$ and solving the resulting system of linear equations. If a certificate is found, it provides a definitive proof of infeasibility.

3. Problem Simplification (Lemma 1 & Theorem 2): To make the problem tractable, the authors establish that for a fixed number of input photons $n$ and heralding photons $m$, it is sufficient to test a single "optimal" configuration to prove infeasibility for all configurations with those photon counts.

   • Optimal Input: A product of single-photon Fock states ($|1, 1, \dots, 1\rangle$) is sufficient to represent any separable $n$-photon input.
   • Optimal Heralding: A pattern where exactly one photon is detected in each heralding mode ($(1, 1, \dots, 1)$) is sufficient to represent any $m$-photon heralding pattern.
   • This reduction allows the problem to be categorized solely by the number of available input photons and the target state, significantly reducing the search space.

Key Contributions and Results
The paper demonstrates the application of this framework to several specific tasks, establishing rigorous lower bounds on resource requirements:

• Bell State Generation: The authors prove that generating a Bell state from a separable three-photon input is impossible. The NulLA algorithm produced an infeasibility certificate at degree 9. This confirms that known solutions requiring four input photons are optimal in terms of photon resources.
• Random Two-Photon States: The technique was applied to hundreds of Haar-random two-photon target states across three and four modes. Infeasibility certificates were found at low degrees (e.g., degree 9) for cases where the theoretical upper bound for the certificate degree was extremely high (e.g., 59,046). This suggests that for many practical cases, the computational cost is far lower than the worst-case theoretical bounds.
• NOON State Generation: The authors analyzed the generation of NOON states (e.g., $|3,0\rangle + |0,3\rangle$) using vacuum heralding. They proved that input states with photons bunched in the same mode (e.g., $|2,1\rangle$) cannot generate these states, establishing that spreading input photons into single-photon modes is a necessary resource.
• Heralded CNOT Gate: The method was extended to verify the resource optimality of a known heralded CNOT gate. By testing a three-photon input with a single heralding photon, the authors proved infeasibility, confirming that at least two ancilla (heralding) photons are required for the gate.
• Extension to Probabilistic Sources: The framework is shown to be adaptable to probabilistic photon-pair sources (e.g., SPDC), where the input is a superposition of different photon numbers. The approach treats different photon-number sectors as a set of simultaneous state-generation tasks.

Significance and Claims
The authors claim that their work provides a rigorous, definitive tool for establishing "no-go" theorems in linear-optical quantum state generation. Unlike numerical optimization or Gröbner basis methods, which may fail to find a solution without proving impossibility, NulLA offers a conclusive proof of infeasibility when a certificate is found.

The significance of this work lies in its ability to:

1. Validate Resource Optimality: It confirms that known solutions (like the 4-photon Bell state generator) are minimal in terms of resource usage.
2. Provide Lower Bounds: It establishes fundamental limits on the number of photons required for specific tasks, guiding experimental design.
3. Automate Feasibility Testing: The systematic nature of the approach allows for the automated testing of large families of target states and gate designs.

The paper concludes that while the theoretical upper bounds for the degree of infeasibility certificates can be prohibitive, practical applications often yield certificates at much lower degrees. This makes the NulLA algorithm a powerful, targeted method for determining the fundamental limitations of optical setups and measurement schemes in the pursuit of universal linear-optical quantum computing. The authors provide a MATLAB implementation of their algorithm on GitHub to facilitate further research.