Approximating Entanglement Based on Abstract Interpretation

Aske Nord Raahauge, Martin Bom Marchioro, Rasmus Ross Nylandsted · 2025

Read Approximating Entanglement Based on Abstract Interpretation by Aske Nord Raahauge, Martin Bom Marchioro, Rasmus Ross Nylandsted (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10056.txt.

Introduction

Aske Nord Raahauge, Martin Bom Marchioro, and Rasmus Ross Nylandsted present in 2025 a static analysis that approximates when quantum bits become entangled. Entanglement is a core trait of quantum systems and matters for speeding circuits and proving programs correct. Exact checks slow down hugely as programs grow, so a sound approximation is valuable.

Their method extends an existing abstract interpretation, a technique that reasons about a program without running it on all inputs. It runs in linear time in their implementation in a functional language. Readers in quantum software get a scalable tool for spotting entanglement early, before costly exact analysis or hardware runs.

Catalog record

CREATORAske Nord Raahauge, Martin Bom Marchioro, Rasmus Ross Nylandsted
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-10056

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximating Entanglement Based on Abstract Interpretation Aske Nord Raahauge, Martin Bom Marchioro, Rasmus Ross Nylandsted Abstract Entanglement is a fundamental property of quantum systems, essential for non-trivial quantum programs. Identifying when qubits become entangled is critical for circuit optimization, and for arguing for the correctness of quantum algorithms. This paper presents a static analysis method for approximating entanglement by extending an already existing abstract interpretation, thus avoiding the exponential slowdown of an exact analysis. The approach is shown to be sound and an implementation is provided in Standard ML with linear-time scalability. 1 Introduction Quantum circuits enable the manipulation of qubits to perform operations that exploit quantum mechanical principles such as superposition and entanglement. Among these, entanglement — a unique quantum property that has no classical counterpart — plays a pivotal role in non-trivial quantum algorithms. Understanding when and how qubits become entangled within a circuit is crucial for advancing various quantum technologies and optimizing their performance. Identifying instances of entanglement formation in quantum circuits has profound implications across several domains, e.g., circuit optimization and error detection, where knowing when qubits are entangled can help optimize gate arrangements and aid in error mitigation by reducing noise in quantum systems. The problem of determining when a quantum system is in an entangled state is dubbed the separability problem , and has previously been shown to be NP-hard [ 3 ] . Instead of an exact analysis, approximation schemes have been proposed to accurately approximate the separability of a quantum state in polynomial time with respect to the number of qubits. We attempt to develop a tool for static analysis of the entanglement of quantum variables, representing qubits in a circuit. Our work represents an implementation of the abstract domain introduced by Perdrix [ 4 ] with the expanded notion of levels as presented by Assolini et al. [ 1 ] . Our intention is to expand the existing quantum computation modeling framework developed for the Advanced Topics in Programming Languages course in Standard ML [ 2 ] , by incorporating this approximate static entanglement analysis. Novel Contributions • A formal adaptation of the QIL -based analysis; conforming to the SML Framework [ 5 ] . • A formal definition of qubit levels, and a derived ruleset for managing such levels [ 1 ] . • A thorough description of soundness for the adapted analysis. • An implementation of the analysis. Code execution The analysis implementation can be found within the directory: atpl-sml-quantum/entanglement_analysis . The main algorithm is implemented in analysis_levels.sml , while auxiliary functions can be found in the file helpers.sml . Lastly, tests are located in test.sml . To run the analysis (with the example provided in Assolini et al [ 1 ] ), simply run $ make And similarly to run the corresponding tests: $ make test 2 Background We recall the basis for understanding entanglement of quantum variables as used by Perdrix [ 4 , 5 ] and Assolini et al. [ 1 ] . We assume that the reader has the academic qualifications corresponding to an introductory course in quantum computation. We will refer to the circuit model for quantum computation, where wires represent individual qubits, which are abbreviated as quantum variables when used in the abstract domain. For denoting quantum states we use ket notation where we denote a linear combination as \ket{\psi}=\alpha\ket{0}+\beta\ket{1} with the probabilities of collapsing to the first and second state being |\alpha|^{2} and |\beta|^{2} respectively. 2.1 Conventions Given the ket description of a quantum state, we will use the term subsystem when referring to a factor in a tensor product, and substate when referring to a term in a summation of kets with non-zero probability/amplitude. For a state composed of m substates, we will refer to \chi_{i}^{k}\in\{0,1\} as the value of the i ’th qubit in substate k . Similarly, we let \neg\chi_{i}^{k} be its opposing value. For example, the state: \ket{\psi}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})\otimes\ket{00} can be decomposed into subsystems \frac{1}{\sqrt{2}}(\ket{00}+\ket{11}) and \ket{00} , with the first consisting of substates \frac{1}{\sqrt{2}}\ket{00} and \frac{1}{\sqrt{2}}\ket{11} , where we have \chi_{0}^{0}=0 , \chi_{1}^{0}=0 , \chi_{0}^{1}=1 and \chi_{1}^{1}=1 . With this, an n qubit state \ket{\psi} composed of m substates with amplitudes \alpha_{k} , could e.g. be written as: \ket{\psi}=\sum_{k=1}^{m}\alpha_{k}\ket{\chi_0^k ... \chi_{n-1}^k}_{k} In all subsequent examples of n qubit states, we will describe the qubits as belonging to a set Q=\{q_{0},...,q_{n-1}\} , where each qubit q_{i} is represented with an index corresponding to its position in the ket-based state description. For the \ket{+} and \ket{-} states, we refer to the symbol \delta\in\{+,-\} with \neg\delta as the opposing state: Such that if \ket{\delta}=\ket{+} , then \ket{\neg\delta}=\ket{-} and vice versa. To denote for which qubit(s) we apply a gate G , we use subscripts such as \texttt{G}_{q_{i}} or \texttt{G}_{q_{i},q_{j}} , when showcasing computations. Further more, we will represent an arbitrary instance of the set of Pauli gates as \sigma\in\{X,Y,Z\} . 2.2 Language Frameworks The entanglement analysis introduced by Perdrix [ 4 ] was originally designed for the high-level QIL quantum language [ 5 ] . In QIL , gates are applied to qubits sequentially, while conditionals and loops can be facilitated by conducting intermediary measurements and evaluating the collapsed result (for more details, see [ 5 ] ). In contrast, the SML Framework provides a circuit/state-based syntax, representing the parallel nature of quantum systems, where the order of gates is ambiguous. It additionally provides no support for intermediary measurement. As opposed to Perdrix’ analysis (where mixed states can occur as a consequence of measurements) the SML Framework operates on pure states only. For our adaptation of the analysis, we are thus likewise limited to the rule-subset relating to pure states. Syntactically, parallel updates are written with infix tensor notation ( ** ) between gates; represented as: I , H , T , X , Y , Z , SW (Swap), CX (CNOT), CY , CZ and so on. Since Perdrix’ rules are defined for the controlled CNOT only, we subsequently ignore all other control-gates in the adapted analysis. Gate compositions, i.e. columns in the quantum circuit, are represented with the operator oo . However, to not clash with the \circ -notation for function composition, we will henceforth represent this with the symbol ++ instead. 2.3 Entanglement We say that a quantum state becomes entangled as a result of some computation, when it enters a superposition of strongly correlated substates, in such a way that the states of the individual quantum variable cannot be described independently of the state of the others. More formally, we follow the definition of entanglement by [ 1 ] and say that a composite quantum state |\psi\rangle_{q_{1},q_{2}}\in\mathcal{H}_{q_{1}}\otimes\mathcal{H}_{q_{2}} is separable if and only if it can be written as |\psi\rangle_{q_{1},q_{2}}\in|\phi_{1}\rangle\otimes|\phi_{2}\rangle for some states |\phi_{1}\rangle\in\mathcal{H}_{q_{1}} and |\phi_{2}\rangle\in\mathcal{H}_{q_{2}} . A state |\psi\rangle_{q_{1},q_{2}} is entangled if and only if it is not separable. 2.4 Standard and Diagonal Basis We recollect the definition of bases as introduced by Perdrix [ 4 ] . Intuitively we say that a given quantum variable q is in the standard basis if for \ket{\psi}_{q}=\alpha\ket{0}+\beta\ket{1} it is given that \alpha=0\lor\beta=0 . Similarly q is in the diagonal basis if it can be represented as \ket{\psi}_{q}=\alpha\ket{+}+\beta\ket{-} and we have that \alpha=0\lor\beta=0 . Where \gamma\ket{\pm}=\gamma\left(\frac{\ket{0}\pm\ket{1}}{\sqrt{2}}\right) More formally the basis

Read the complete text