# Techniques: Benincasa-Dowker-Glaser causal set actions by quantum counting

## What the paper contributes (one paragraph)

The paper gives a quantum algorithm that computes the Benincasa-Dowker-Glaser (BDG) causal set action, the causal set analogue of the Einstein-Hilbert action, in arbitrary spacetime dimension. For a causal set of n elements it runs in time soft-O(n^2) with O(n) qubits, estimating the action to within O(epsilon n) error with high probability, an asymptotically optimal result that beats the O(n^3) and O(n^2.8074) classical methods. The algorithm works by encoding the adjacency matrix into a uniform superposition over an O(n^2)-size subset of basis states, applying parametrised oracle circuits that test the discrete volume between element pairs, and counting how many pairs have each volume. The counting uses a two-stage variant of Grover-only approximate counting whose error scales as the square root of the true count. The paper also analyses a constant-factor-improved classical random-sampling estimator for the same abundances.

## Techniques offered

- **Quantum algorithm for the BDG causal set action via quantum counting** - A new soft-O(n^2)-time, O(n)-qubit quantum algorithm that estimates the d-dimensional BDG action by counting order-interval abundances, supplying a quadratically faster routine for evaluating discrete gravitational actions and, more generally, abundances of fixed-size order intervals in a partial order.
  - guarantee: statistical bound; output S-hat satisfies |S-hat - S| < O(epsilon n) with probability at least (1 - delta)^{n_d}, in running time soft-O(n^2 epsilon^-1 log(delta^-1)) and O(n) qubits, with the n^2 scaling shown asymptotically optimal.
  - quote: "Our main contribution is a quantum algorithm to estimate the value of the $d$-dimensional Benincasa--Dowker--Glaser causal set action up to an $\bigO(\varepsilon n)$ error in $\softO(n^{2} \varepsilon^{-1})$ time."

- **Two-stage approximate quantum counting with square-root error** - An adaptation of Grover-only (quantum-Fourier-transform-free) approximate counting that runs a rough first count to tune the error parameter, then a refined count, yielding an abundance estimate whose absolute error scales with the square root of the true count; a reusable estimation primitive for any Grover-style amplitude/count problem.
  - guarantee: statistical bound; estimate K-hat satisfies |K-hat - K| < epsilon sqrt(K) with probability at least 1 - zeta, using fewer than O(epsilon^-1 sqrt(N) log(1/zeta)) oracle queries and O(log N) qubits.
  - quote: "To this end, in \cref{sec:abundance_counting_alg} we adapt the simplified quantum counting algorithm of \textcite{aaronson2020quantum} (which makes no use of the quantum Fourier transform and relies solely on Grover iterations) to perform two stages: an initial rough estimate of the count which is used to feedback and tune the target error parameter, followed by a final count using this updated parameter."

- **Efficient data-superposition preparation over an arbitrary index subset** - A state-preparation and compilation method that builds a uniform superposition over an arbitrary O(n^2)-size subset of basis states (here the row/column pairs of an adjacency matrix) in a minimal-dimensional register and maps it into a larger data register using low-depth multi-controlled multi-target NOT gates, supplying a reusable classical-data loading block for Grover-style algorithms.
  - guarantee: static circuit-resource bound; the uniform superposition of \cref{eq:general_superposition} is prepared by a circuit of depth O(N log(m log N)) using ceil(log2 N) - 1 reusable ancilla qubits and total width m + 2 ceil(log2 N) - 1.
  - quote: "The uniform superposition of \cref{eq:general_superposition} can be prepared by applying a circuit of depth $\bigO(N \log(m \log{N}))$ using $\lceil \log_{2}{N} \rceil - 1$ reusable ancilla qubits, where all qubits are initially prepared as $\ket{0}$."

## Where it could apply

- Target primitive(s): quantum counting / amplitude estimation; Grover-style unstructured search and sampling; classical-data loading (state preparation) feeding such primitives
- Target application group(s): platforms_tooling; quantum gravity and discrete-geometry simulation (sum-over-causal-sets dynamics); any combinatorial counting task over a partial order or sparse Boolean adjacency matrix
- Code family / hardware assumptions: fault-tolerant, logical-qubit hardware (large-scale FTQC); gate-model with low-depth multi-controlled Toffoli compilation and (bounded) fan-out gates; not surface-code or qLDPC specific; near-term NISQ or adiabatic realisation only speculative

## Caveats

The deliverable is a quantum algorithm, suppliable as a routine rather than an assurance over an external result; its guarantees are the internal accuracy and resource bounds quoted above. It assumes large-scale fault-tolerant quantum hardware that does not yet exist, and assumes a classical causal-set description allowing constant-time lookup of each element's past and future. The order-interval oracle circuit itself is bespoke to the discrete-volume (dot-product equals k+2) test and is reported as a component of the main algorithm rather than as a standalone general-purpose technique, so it is folded into the first bullet. The companion classical random-sampling estimator gives only a constant-factor improvement with no asymptotic speedup and is not a quantum technique.