# Integrated Information in Relational Quantum Dynamics (RQD)
## Appendix A Computational Scalability and Practical Estimators for \(\Phi\)
### Fixed-Parameter and Symmetry Reductions  
Although the worst-case cost of bipartition search is exponential, in practice, many quantum states of interest have structure that can be exploited to reduce the effective search space to something more tractable. Here we outline three complementary heuristics--_tensor-product symmetry_, pre-clustering via local-cut bounds, and branch-and-bound pruning--that together enable the exact or near-exact evaluation of \(\Phi\) for systems up to about \(n\lesssim 30\) on commodity hardware. These techniques can cut down the number of candidate cuts by orders of magnitude, turning an otherwise hopeless exponential search into a feasible computation. * **Tensor-product symmetry:** If the global state \(\rho\) is invariant under a nontrivial subgroup \(G\subseteq S_{n}\) of subsystem permutations (for example, in a translationally invariant chain or any scenario with identical subsystems), then many bipartitions are equivalent under \(G\). In such cases, one needs only to evaluate \(D_{QIS}(\rho|\rho_{A}\otimes\rho_{B})\) for one representative from each orbit of the \(G\)-action on the set of cuts. By computing the automorphism group of the interaction graph and selecting canonical representatives of each orbit, one can avoid redundant evaluations. This symmetry reduction often lowers the number of distinct bipartitions by one to two orders of magnitude in typical many-body states, dramatically shrinking the search space. * **Pre-clustering via local-cut bounds:** Strongly correlated subsets of subsystems can be merged into effective \"supernodes\" to coarsen the problem before doing the full search. A simple approach is to use mutual information as a proxy for correlation: first compute the pairwise mutual information \(I_{ij}=S(\rho_{i})+S(\rho_{j})-S(\rho_{ij})\) for every pair of subsystems. Then apply a single-linkage hierarchical clustering, merging any two subsystems (or clusters) whose \(I_{ij}\) exceeds a chosen threshold \(\tau\). This groups together highly entangled units. Next, perform the \(\Phi\) search on the reduced system of supernodes, treating a cluster of size \(m\) as a single node. Only if a coarse-grained bipartition's divergence is promisingly low, for example, below the current best (\(\Phi\)) do we \"open up\" the cluster to evaluate finer partitions on the original subsystems. Because clustering absorbs much of the internal entanglement, the effective number of nodes \(n_{\text{eff}}\) can be much smaller than \(n\) (for instance, one finds \(n_{\text{eff}}\approx n/3\) in 1D chains with a reasonable \(\tau\approx 0.1\)). This translates to searching only \((\genfrac{}{}{0.0 pt}{}{n_{\text{eff}}}{\lfloor n_{\text{eff}}/2\rfloor})\) partitions instead of \((\genfrac{}{}{0.0 pt}{}{n}{\lfloor n/2\rfloor})\), an enormous reduction. * **Branch-and-bound pruning:** A final speedup is achieved by pruning the exhaustive search via a lower-bound estimate on partial cuts. The algorithm builds bipartitions incrementally in a depth-first manner. Suppose at some step we have a partial cut \(A_{k}\), with \(k\) subsystems assigned to the \(A\) side, and the rest of \(B_{k}\) is undetermined. One can efficiently compute a provable lower bound on the divergence for any completion of this partial cut. In particular, using the joint convexity and subadditivity of \(D_{Q|S}\), one finds \[D_{QIS}\Big{(}\rho\left\|\rho_{A_{k}}\otimes\rho_{B_{k}}\right)\ \geq\ \sum_{i\in A_{k}}\ \min_{j\in B_{k}}\ D_{QIS}\Big{(}\rho_{ij}\left\|\rho_{i} \otimes\rho_{j}\right).\] (22)
* This bound (computable in \(O(k,(n-k))\) time for each partial cut) gives a threshold that any full bipartition extending \(A_{k}\) will exceed. If the bound is larger than the best divergence found so far (\(\Phi_{\text{best}}\)), we can abandon all completions of \(A_{k}\) without missing the global minimum. In effect, large swaths of the search tree are pruned away whenever a partial assignment cannot possibly lead to a better solution.