[Automatic translation by Google]
Please provide your feedback about the website at feedback@apc.iisc.ernet.in
This project has developed a new analytical framework for designing and ruling out quantum photonic experiments. By translating optical apparatus into edge-coloured, weighted graphs, the work replaces parts of a rapidly expanding computational search with structural theorems, efficient algorithms, and rigorous impossibility certificates. The project produced four linked research papers across Quantum, the Electronic Journal of Combinatorics, MFCS and FSTTCS, as well as the 2022 EUR 1,000 Quantum-Graph Best-Paper Award.
Background and scientific challenge
Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states of fundamental importance to quantum information science, with potential applications in quantum communication, cryptography, and distributed quantum computing. Increasing both the number of entangled particles and the dimensionality of these states is an important but exceptionally difficult objective in experimental quantum optics.
In 2017, Mario Krenn, Xuemei Gu, and Anton Zeilinger showed that a large class of quantum photonic experiments can be represented using edge-coloured, edge-weighted graphs [1]. Zeilinger subsequently shared the 2022 Nobel Prize in Physics for pioneering experiments with entangled photons and quantum information science [2]. This connection created an unusual opportunity: a frontier problem in experimental quantum optics could be studied using theoretical computer science and graph theory.
From a photonic experiment to a graph
In this representation, photon detectors become vertices, photon-pair sources and optical paths become edges, photonic modes become edge colours, and probability amplitudes become complex-valued edge weights. A simultaneous multiphoton detection event corresponds to a perfect matching. The dimension of the GHZ state generated by an experiment is encoded by the number of valid monochromatic outcomes represented by the graph.
The graph is therefore not merely an analogy; it is a mathematical encoding of a realisable optical experiment. The automated methods based on AI, SAT solvers and numerical search can identify small designs, but their search spaces grow rapidly. The project’s objective was to determine analytically which architectures are possible, which are impossible, and where computation should be concentrated.
Major research outcomes:
The grant produced a coherent sequence of four papers that progressively established the mathematical foundations of this graph-based approach.
This paper gives a complete structural characterisation of the relevant experiment graphs in the regime without destructive interference. It also provides an O(|V||E|)-time algorithm for determining their matching index. The result resolves the relevant Krenn-Gu question for this important class and converts a physics-motivated existence problem into a tractable graph algorithm.
The researchers introduced local-sparsification and edge-pruning methods and proved that, within a broad class represented by simple graphs, an n-particle GHZ state of dimension greater than n/sqrt(2) cannot be generated. This was the first non-trivial analytical upper bound for this class of experiments, advancing beyond small instances previously checked by SAT computation and helping identify leaner experimental resource requirements.
This work treats the fully general model with multiple edges, bichromatic edges, complex amplitudes and destructive interference. It proves the conjecture for graphs of vertex connectivity at most two and for cubic graphs, and shows that any smallest counterexample must be four-connected. These theorems eliminate large families of candidate experiment graphs and sharply restrict automated searches for feasible designs.
This paper links realisable GHZ dimension directly to edge connectivity, vertex connectivity, and maximum degree. Among its bounds are mu(G) <= lambda(G) and mu(G) <= 2^(kappa(G)-1) + C(kappa(G),2). It also supplies purely combinatorial proofs for six- and eight-vertex cases that had previously required SAT computation, strengthening the project’s analytical framework for identifying feasible and infeasible architectures.
Outstanding nature and impact:
The principal outcome is a new way to reason about the capabilities and limitations of quantum photonic systems. Rather than relying only on increasingly expensive searches, the framework proves impossibility for whole families, establishes upper bounds, and identifies the restricted graph classes in which new experimental configurations may still be found.
Recognition and funding leverage:
The quality and originality of the research were recognised through the 2022 EUR 1,000 Quantum-Graph Best-Paper Award [7]. With a sanctioned budget of approximately INR 41.89 lakhs, the project has produced four connected publications in respected quantum-science, graph-theory, and theoretical-computer-science venues. It demonstrates how focused foundational funding can generate internationally visible results while also making computational and experimental exploration more targeted and resource-aware.
In summary, the project converts an experimentally motivated quantum problem into precise mathematical structure, reduces the space of possible experiments, and provides a rigorous foundation for future discoveries in high-dimensional photonic entanglement.
References and evidence:
[1] Krenn, Gu and Zeilinger, PRL 119, 240403 (2017); [2] Nobel Prize in Physics 2022; [3] Electronic Journal of Combinatorics 33(3), P3.21 (2026); [4] Quantum 8, 1396 (2024); [5] MFCS 2024, LIPIcs 306, Article 41; [6] FSTTCS 2026 acceptance and publication list; [7] Quantum-Graph Best-Paper Award. Grant record: Government of India Science and Technology portal.
Faculty: L Sunil Chandran
