Certain and Possible Subgraphs: Quantum Listing on Similarity Graphs Built from Clipped Sensors

Many image-restoration and analysis methods compare every small patch of an image with every other patch. They then work with the resulting similarity graph, where two patches are connected if they look alike. This graph is never stored. Each edge is computed on demand, so it has on the order of $n^2$ potential edges for $n$ patches. That is exactly the setting where quantum query algorithms for finding and listing small subgraphs, such as triangles and cliques, can in principle use fewer edge evaluations than any classical method. Sensor saturation breaks this picture in a specific, measurable way. A pixel is saturated when its true brightness exceeded what the sensor could record and its value was clipped to the maximum. Every fully clipped patch records the same flat value, so a bright plateau of $s$ patches appears to form an $s$-clique. That clique alone contributes about $s^3/6$ triangles, and any algorithm that lists triangles must write every one of them down. Worse, those edges are not real evidence. Two patches that both read $V_{\max}$ may hide completely different scene content above the clipping level.

We propose treating the similarity graph of a clipped image as three-valued. Each edge is either certainly present, certainly absent, or undetermined because of clipping. We then change the listing problem to match. Witnesses supported by unclipped evidence are listed one by one. Witnesses that exist only because of clipping are listed once per group of clipping-equivalent patches, together with a multiplicity count. This keeps the output governed by the size of a much smaller quotient graph rather than by the combinatorics of the plateaus. The note has two jobs. It asks whether, and at what scale, quantum listing actually beats the classical alternative on this reduced problem. It also asks whether the certain-versus-possible split is itself useful: specifically, whether it predicts where learned restoration models hallucinate content.

Core Claim

The claim has two halves, and they can succeed or fail separately.

The algorithmic half concerns the query model, in which an algorithm is charged one unit per patch-pair comparison. We claim that listing on the three-valued graph modulo clipping-equivalence has an output size set by the number of clipping-equivalence classes and the certain witnesses. That output is typically orders of magnitude below the raw triangle count on saturated images. With this reduced output, output-sensitive quantum listing becomes non-trivially cheaper than classical pairwise evaluation once the quotient graph is large and dense.

The empirical half is independent of any quantum hardware. We claim that the number of undetermined edges touching a patch predicts where restoration models produce plausible but wrong content.

Formally, a patch $p$ has a set $C_p$ of clipped pixels. Each clipped pixel is known only to lie in an interval: $[V_{\max}, \infty)$ at the top of the range, or below the noise floor at the bottom. The squared distance between patches $p$ and $q$ is therefore only known to lie in an interval $[d^{\mathrm{lo}}_{pq}, d^{\mathrm{hi}}_{pq}]$. Given a similarity threshold $\tau$, the edge is classified as follows:

$$ e_{pq} = \begin{cases} \text{certain} & d^{\mathrm{hi}}_{pq} \le \tau \\ \text{absent} & d^{\mathrm{lo}}_{pq} > \tau \\ \text{undetermined} & \text{otherwise.} \end{cases} $$

Two fully clipped patches have $d^{\mathrm{lo}}=0$ and $d^{\mathrm{hi}}=\infty$. Their edge is therefore undetermined, not certain. This is the formal version of the ambiguity that exposure and reflection papers keep running into: a flat white region cannot be told apart from a clipped light source.

The three-valued graph can be represented by two ordinary graphs. The "certain" graph keeps only certain edges. The "possible" graph also treats undetermined edges as present. Each graph is exposed as a standard adjacency-matrix oracle, so existing quantum machinery applies unchanged.

Relation to Prior Work

The saturation literature motivates the problem, and it also constrains what may be claimed. RAW Image Reconstruction Using a Self-Contained sRGB-JPEG Image with Only 64 KB Overhead argues that once sensor readings are clipped, inverting the capture process is impossible. Model-Based Image Signal Processors via Learnable Dictionaries names the resulting flat plateaus the "ceiling effect" that disables inverse processing. Towards Perfection: Building Inter-component Mutual Correction for Retinex-based Low-light Image Enhancement shows that splitting an image into illumination and reflectance collapses in these dead zones. Color Shift Estimation-and-Correction for Image Enhancement shows that hue is lost once any channel clips.

On the learned side, Revisiting Single Image Reflection Removal in the Wild, Single Image Reflection Separation via Dual-Stream Interactive Transformers and Flare7K: A Phenomenological Nighttime Flare Removal Dataset report that deep models only soften artifacts or paint in plausible textures under saturation.

Together these papers rule out any claim that our method recovers clipped content, and we make no such claim. What they leave open is a way to state, patch by patch, which structural relationships in an image are supported by recorded evidence and which are artifacts of clipping. The three-valued graph supplies that.

The closest restoration work is Overexposure Mask Fusion: Generalizable Reverse ISP Multi-Step Refinement. It feeds binary saturation masks into a reverse camera-processing network, operating per pixel. We instead use saturation to decide which relationships between patches are certain, and we reason about the combinatorial structure those relationships form.

The quantum side supplies the method. Quantum algorithms for the triangle problem detects triangles with $\tilde{O}(n^{13/10})$ adjacency queries. It does this with a quantum walk over subsets of vertices, meaning a search that moves through groups of vertices one swap at a time while remembering the edges among them. Extended Learning Graphs for Triangle Finding tunes such walks to the spread of vertex degrees. That matters here because plateau classes create exactly the kind of extreme degree heterogeneity it targets. Applications of the quantum algorithm for st-connectivity warns that naively nesting Grover searches (the basic quantum search primitive) adds overhead. This constrains us to use walk-based detection as the inner routine rather than nested search. Quantum property testing in sparse directed graphs combines Grover search with classical breadth-first expansion, which is the template for our hybrid design: a cheap classical pass plus quantum search.

Every one of these works targets detection or sampling on a clean Boolean oracle. None addresses listing when the witness set is dominated by structurally redundant copies, and none addresses oracles with an undetermined outcome.

The research file found no prior work joining quantum subgraph algorithms with sensor saturation. The nearest matches for "saturation" are unrelated: Cycle Saturation in Random Graphs is extremal combinatorics. Saturation in Snapshot Compressive Imaging and Mixed one-bit compressive sensing with applications to overexposure correction for CT reconstruction treat clipped measurements as constraints in classical signal recovery. That last paper is conceptually closest in treating clipped readings as one-sided constraints. We borrow that interval view, but apply it to relationships between patches rather than to recovering the signal.

Research Program

The first component is a classical pass that costs $O(n)$. For each patch, we compute its clip signature: which pixels are clipped, and the recorded values of the unclipped ones. We then hash patches into clipping-equivalence classes, where two patches are equivalent when they agree on unclipped pixels and share a clip pattern. This step is deliberately classical. Any quantum listing algorithm must at least read its $n$ vertices, so this pass never dominates the cost.

The second component is theory. We will bound the output size of quotient listing in terms of the number of equivalence classes $k$ and the number of certain witnesses $t_c$. We will then derive the quantum query cost of listing certain triangles individually and possible-only triangles at class level. The inner routine is the walk-based detector, repeated with found witnesses excluded. We will state honestly where the known cost of repeated detection, which grows with the number of witnesses, makes the quantum algorithm lose to classical evaluation. We will not claim a new lower bound unless we prove one.

The third component is implementation. We simulate the algorithms as exact query counters on real images: the classical parts run for real, and the quantum subroutines are charged their standard query costs. This lets us plot query counts against $n$ on actual clipped data and not only on random graphs.

The fourth component, the restoration check, asks whether the density of undetermined edges around a patch predicts restoration error.

Baselines

The naive reference point is classical: evaluate all $n^2/2$ patch pairs, build the ordinary thresholded graph from the recorded values, and list every triangle. It is run on the same patches, with the same threshold and patch size. It sets the raw output size that the quotient formulation must shrink. It also shows how much of the triangle count comes from plateaus. Beating it means reducing output size and pairwise evaluations by at least an order of magnitude on images with substantial saturation.

The strongest competitor is classical, and it is the real threat. It performs the same $O(n)$ clipping-equivalence hashing, then evaluates all pairs on the quotient graph with $k$ vertices and lists witnesses classically. It receives the same threshold, patch size and preprocessing as our method. Its cost is on the order of $k^2$ similarity evaluations plus output. The quantum pipeline beats it only if its simulated query count falls below this at quotient sizes that actually occur in the benchmark images. If that crossover lies beyond every image we test, we will report it as the main finding.

The strongest existing quantum method is the Johnson-graph triangle walk of Quantum algorithms for the triangle problem, with the degree-adaptive tuning of Extended Learning Graphs for Triangle Finding. It is run directly on the full possible graph, without quotienting, and made to list by repeated detection. The only reported figure in the file is $\tilde{O}(n^{13/10})$ queries for detection, from the first of these papers. No reported result was found on Lacuna for listing cost on image-derived graphs. Beating this baseline means a lower simulated query count whenever plateau classes are large.

Two ablations isolate the key ingredients. The first applies quotienting but uses a two-valued oracle that treats clipped equality as a certain edge. This isolates the value of the three-valued edge. The second uses the three-valued oracle without quotienting. This isolates the value of class-level output.

Why not just…?

Why not just collapse identical patches classically and list classically? This is a serious alternative, and the research file's own assessment agrees: megapixel images are scanned in milliseconds. For ordinary photographs we expect it to win on wall-clock time, and the quantum claim applies only to query counts on very large implicit graphs. The experiments measure $k$ on real images and locate the crossover. If $k$ stays small, the honest conclusion is that the three-valued, quotient formulation is the contribution and the quantum part is not needed at practical scales.

Why not just discard every patch containing a clipped pixel, as mask-based pipelines do? Masking in the style of Overexposure Mask Fusion avoids the blowup. It also deletes the partially clipped boundary patches, which are exactly where restoration must decide what to paint. We will measure what fraction of patches lie within a few pixels of a plateau and are lost by masking. We will also test whether certain edges from those patches carry predictive signal in the restoration check.

Why not just use a k-nearest-neighbour graph, which caps degree and removes the cubic blowup? Capping the number of neighbours bounds the output. Inside a plateau, however, all candidates tie, so the neighbour lists are decided by arbitrary tie-breaking. Boundary patches then have their neighbour lists crowded with plateau twins. We will measure the share of boundary patches' neighbour slots consumed by fully clipped patches. If that share is small, this alternative undercuts our motivation, and we will say so.

Why not just bracket exposures? Bracketing is inapplicable to single-shot captures such as the nighttime flares in Flare7K. It also creates its own artifacts across views, as reported in Learning Neural Exposure Fields for View Synthesis. Our scope is single captures.

Proposed Experiments

We use four sets of data. The first two are Flare7K and the SIRR-in-the-wild pairs from Revisiting Single Image Reflection Removal in the Wild, both of which provide clean references. The third is the multiple-exposure correction benchmarks used by ECMamba. The fourth is the RAW data of Removing Reflections from RAW Photos, where the true clipping level of the sensor is known rather than guessed.

For each image and each patch size, we report the following quantities. From the naive baseline: the raw triangle count and the share of it produced by fully clipped patches. From our formulation: the quotient size $k$, the certain-triangle count, and the class-level output size. For costs: simulated quantum query counts against classical evaluation counts. Finally, we extrapolate the query curves to locate the crossover $n$.

The first decisive check concerns output reduction. If quotient output is not at least ten times smaller than the raw output on saturated images, the listing formulation adds nothing.

The second decisive check is the restoration test. We run published flare- and reflection-removal models and compute per-patch error against the clean references. We then compare how well error is predicted by the number of undetermined edges touching a patch versus a plain per-pixel saturation mask, using rank correlation and area under the curve for flagging high-error patches. If undetermined-edge density does not add predictive power beyond the mask, the three-valued graph is not earning its complexity.

The third check addresses the quantum claim. We report the crossover quotient size against the classical quotient baseline, and we state plainly whether any benchmark image reaches it.