SAT synthesis of photonic state-preparation experiments
Can the search for an interpretable photonic experiment that prepares a prescribed quantum state be formulated and solved exactly, rather than relying only on continuous optimization and local minima?
Progress summary
The problem has a useful exact discrete-search component, but preparing every target state still requires numerical optimization, so the general problem remains open.
The problem asks whether interpretable photonic experiments preparing prescribed quantum states can be synthesized exactly rather than by continuous optimization alone. A 2022 formulation answers this affirmatively only for the Boolean-search component, not for the complete physical synthesis pipeline.
Known results
- The algorithm Klaus encodes graph-based photonic state preparation as SAT and can certify impossibility when the encoded formula is unsatisfiable (2022).
- Satisfiability is not sufficient for physical preparation because interference between perfect matchings and edge weights is incompletely represented; numerical optimization remains necessary (2022).
- For a GHZ-state construction, instances with up to and were computationally unsatisfiable; the corresponding broader conjecture remains unresolved for negative and complex weights.
- The positive-weight special case was solved by Ilya Bogdanov in 2017.
2024 constructability follow-up
An analytical follow-up used local sparsification of experiment graphs to study constructability of complex entangled states, but the available report does not establish a general SAT-synthesis theorem or settle all prescribed states.
Current status (as of March 2026): SAT provides an exact and interpretable discrete filtering or impossibility certificate, but exact synthesis of arbitrary prescribed photonic states remains open because satisfiable instances still require continuous physical validation and optimization.
Solutions 0
No solutions have been posted yet.