Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum von Neumann Machine and the Cost of Coherent Programmes

Hutan Ashrafian

Published Oct 31, 2026• 0 citations
Publisher

Abstract

A quantum von Neumann machine that retains its stored programme in superposition must execute the selected operations without destroying coherence between programme branches, creating a resource requirement that cannot be assessed by examining each programme separately. I establish this distinction for programmes that select controlled-Z operations on the edges of a graph. Every classically selected programme uses only Clifford operations, yet coherent execution requires a number of injected non-Clifford T states proportional to the programme length for every fixed normalised diamond-distance tolerance below one half. For a graph with m edges and n active data vertices, the lower bound for exact execution is m + n states, whilst an explicit implementation uses at most 4m. The lower bound permits arbitrary programme-dependent phases, stabilizer workspace, measurements and adaptive control. Its extension to imperfect execution bounds both the probability of substantial resource consumption and the expected consumption, without imposing a separate limit on workspace or measurement count. The proof derives a uniform bound on Pauli expectations of the joint programme-data output and uses its stabilizer subspaces to constrain every low-resource trajectory. A supporting criterion identifies precisely when a Clifford instruction library admits an exact Clifford interpreter under the chosen binary programme encoding. These results separate the cost of interpreting coherent instructions from the cost of the operations selected by a classical programme, providing a quantitative constraint on compilation and resource estimation for stored-programme quantum computation.

DOI
10.5281/zenodo.23841118

Related papers

Nearly Optimal T-Count for Symmetry-Based Quantum State Purification

Jialiang Tang, Junhong Nie, Keming He +2 more

Protecting quantum information from noise is essential for reliable quantum computation and quantum memories. Quantum state purification addresses this challenge by processing multiple noisy copies of an unknown quantum state to produce an output state of higher fidelity. Here we establish nearly tight upper and lower bounds on the non-Clifford resources required to implement the symmetric-projection purification protocol. For $n$ copies of a $d$-dimensional system, we construct a Clifford+T circuit that block-encodes the symmetric projector with operator-norm error at most $ε$ using $\widetilde{O}(n)$ T gates, where the tilde-$O$ notation suppresses polylogarithmic factors in $n$, $d$, and $1/ε$. Conversely, using stabilizer nullity, we prove that any Clifford+T implementation of such a block encoding with error $ε<\frac{1}{2}\sqrt{1-1/n}$ requires at least $2n-2$ T gates, even allowing arbitrary positive normalization and clean stabilizer ancillas. Taken together, these results establish the nearly optimal scaling of non-Clifford cost with the number of copies and uncover the fundamental resource requirements for coherent symmetry projection in quantum state purification.

quant-pharXiv:2610.12098•Oct 9, 2026•0 citations

Lower bounds on the non-Clifford resources for quantum computations

Michael E. Beverland, Earl T. Campbell, Mark Howard +1 more

Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.

arXiv:1904.01124•Quantum Science and Technology•Apr 15, 2020•192 citations

A T-count Zero Protocol for Heralded W-state Preparation via Clifford-only Gates

Amrita Mitra

Abstract The W state is a key resource for quantum communication and distributed quantum computing. Its entanglement survives the loss of any single qubit. Preparing the W state exactly is nevertheless hard in fault-tolerant architectures. The amplitude 1/√3 lies outside the ring Z[1/√2, i]. So no Clifford+T unitary can prepare the three-qubit W state exactly, and deterministic circuits must approximate the required rotation at a T-count that grows as log(1/ϵ). We present a heralded protocol that prepares the three-qubit W state exactly using Clifford gates and a single non-Clifford operation. A shallow Clifford circuit with two CNOT gates first prepares an equal superposition of |001⟩, |010⟩, |100⟩ and |111⟩. A logical-AND measurement on one ancilla then removes the |111⟩ component without disturbing the remaining coherent superposition. The protocol succeeds with probability 3/4, a failed attempt leaves the known product state |111⟩, and each attempt consumes four T gates or one |CCZ⟩ magic state. This gives an expected cost of about 5.33 T gates independent of target precision. We prove that some non-Clifford step is necessary, and by exhaustively enumerating all 315,057,600 six-qubit stabilizer tensors we show that no post-selected Clifford circuit with three or fewer T gates outputs the W state. Every heralded Clifford+T preparation of the W state therefore uses at least four T gates per successful run, and our protocol attains this bound. The protocol uses 6 to 19 times fewer T gates than gate synthesis at precisions between 10−3 and 10−10. We compare it with a deterministic circuit using an exact repeat-untilsuccess rotation, which achieves a slightly lower expected cost of about 4.67 T gates, and discuss implementation in modular architectures and extensions to N-qubit W states. Note on this version. This version replaces and corrects the first version of this preprint (“A Tcount Zero Protocol for Heralded W-state Preparation via Clifford-only Gates”). The claim there that the W state can be prepared with Clifford gates alone is incorrect: as shown here, some non-Clifford step is necessary, and at least four T gates are needed per successful run.

•Jul 22, 2026•0 citations

Minimum Quantum Storage from Incomplete Channel Observations

Jeremy Rodgers

How much quantum storage must a hidden implementation retain when experimental observations leave its structure undetermined? This paper establishes exact minimum quantum-storage requirements across all implementations compatible with specified channel observations. The resource is the worst-input expected logarithm of retained quantum dimension across one controlled temporal cut, with unlimited classical records available at no cost. For the channel dimension measure introduced by Cope and Uola, the paper proves their suggested minimax equality relating minimum storage to output Schmidt measure and extends it to every nonempty compact convex set of compatible channels. One common input enforces the resource minimum across all compatible implementations. A finite optimal implementation exists, although an optimal entangled probe need not. For qubit channels, four measured coefficients determine an exact, attained minimum without assuming channel covariance or unitality. An explicit five-Kraus construction attains 99/169, while a separate analytical certificate proves that every compatible implementation must use nontrivial quantum storage with at least that probability on the same specified input. A second exact formula uses only two Pauli-transfer coefficients and yields a minimum storage requirement of 0.58 when both coefficients are jointly constrained to the interval [0.79, 0.81]. The paper also presents semidefinite optimization over compatible experimental uncertainty regions. The results require calibrated quantum inputs and outputs, concealed preparation labels, and accounting for every quantum carrier across the storage cut. They constrain storage resources without reconstructing the hidden implementation or certifying environmental non-Markovianity. Motivated by Shadow Theory’s source/readout distinction, the proofs use standard quantum mechanics and quantum-information mathematics. Version 1.1 includes complete proofs, explicit attaining constructions, worked examples, and discussion of experimental assumptions and limitations. No experimental data are reported.

•Sep 6, 2026•0 citations

Cost-optimal single-qubit gate synthesis in the Clifford hierarchy

Gary J. Mooney, Charles D. Hill, Lloyd C. L. Hollenberg

For universal quantum computation, a major challenge to overcome for practical implementation is the large amount of resources required for fault-tolerant quantum information processing. An important aspect is implementing arbitrary unitary operators built from logical gates within the quantum error correction code. A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision by assembling sequences of logical gates chosen from a small set of universal gates that are fault-tolerantly performable while encoded in a quantum error-correction code. However, current procedures do not yet support individual assignment of base gate costs and many do not support extended sets of universal base gates. We analysed cost-optimal sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the canonical Clifford+ T set of base gates and compared them to when additionally including Z -rotations from higher orders of the Clifford hierarchy. Two approaches of assigning base gate costs were used. First, costs were reduced to T -counts by recursively applying a Z -rotation catalyst circuit. Second, costs were assigned as the average numbers of raw (i.e. physical level) magic states required to directly distil and implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to 54±3% when using the Z -rotation catalyst circuit approach and by up to 33±2% when using the magic state distillation approach. In addition, we investigated observed limitations of certain assignments of base gate costs by developing an analytic model to estimate the proportion of sets of Z -rotation gates from higher orders of the Clifford hierarchy that are found within sequences approximating random target gates.

arXiv:2005.05581•Quantum•Feb 15, 2021•7 citations

Quantifying Distinguishable Worlds in Everett's Multiverse: Quantum Darwinism and Finite-Memory Records of Changing von Neumann Machines

Hutan Ashrafian

Everettian quantum mechanics describes alternative histories within one evolving quantum state, while quantum Darwinism relates their accessibility to information retained in environmental records. I examine how finite record memory constrains the number of distinguishable histories and the organisation of their conditional ancestry. When d + 1 histories must each be decoded from a d-dimensional fragment with success d/(d + 1), the established discrimination optimum forces a regular-simplex geometry. Its conditional mixtures then determine exact ancestral edge costs and a joint criterion for the permissible topology, depth, total variation and largest step. In the three-history binary example, equally weighted labels decoded with success 2/3 require 61.6% greater minimum conditional variation in a qubit than in an optimally designed three-dimensional record. For six histories, minimising total variation and minimising the largest step select different genealogies. Quantitative stability estimates show that the additional constraint persists under sufficiently small departures from ideal decoding and weights. At this threshold, trace-distance contraction prevents a fixed channel acting only on an unrestricted optimum from compressing it into the smaller record at unchanged accuracy, although an explicit controlled preparation realises the alternative encoding. A von Neumann-inspired application distinguishes hereditary function, present configurations and retained mutation histories, and a comparison of finite and infinite counts separates these quantities from cosmological multiplicity. The resulting theory makes the limitations of environmental memory consequential for readable branching while keeping conditional variation distinct from physical rates of change. Its bounds apply to specified records and histories without assigning an absolute number of worlds since the universe’s beginning.

•Oct 31, 2026•0 citations
A quantum von Neumann machine that retains its stored programme in superposition must execute the selected operations without destroying coherence between programme branches, creating a resource requirement that cannot be assessed by examining each programme separately. I establish this distinction for programmes that select controlled-Z operations on the edges of a graph. Every classically selected programme uses only Clifford operations, yet coherent execution requires a number of injected non-Clifford T states proportional to the programme length for every fixed normalised diamond-distance tolerance below one half. For a graph with m edges and n active data vertices, the lower bound for exact execution is m + n states, whilst an explicit implementation uses at most 4m. The lower bound permits arbitrary programme-dependent phases, stabilizer workspace, measurements and adaptive control. Its extension to imperfect execution bounds both the probability of substantial resource consumption and the expected consumption, without imposing a separate limit on workspace or measurement count. The proof derives a uniform bound on Pauli expectations of the joint programme-data output and uses its stabilizer subspaces to constrain every low-resource trajectory. A supporting criterion identifies precisely when a Clifford instruction library admits an exact Clifford interpreter under the chosen binary programme encoding. These results separate the cost of interpreting coherent instructions from the cost of the operations selected by a classical programme, providing a quantitative constraint on compilation and resource estimation for stored-programme quantum computation.
Protecting quantum information from noise is essential for reliable quantum computation and quantum memories. Quantum state purification addresses this challenge by processing multiple noisy copies of an unknown quantum state to produce an output state of higher fidelity. Here we establish nearly tight upper and lower bounds on the non-Clifford resources required to implement the symmetric-projection purification protocol. For nnn copies of a ddd-dimensional system, we construct a Clifford+T circuit that block-encodes the symmetric projector with operator-norm error at most εεε using O~(n)\widetilde{O}(n)O(n) T gates, where the tilde-OOO notation suppresses polylogarithmic factors in nnn, ddd, and 1/ε1/ε1/ε. Conversely, using stabilizer nullity, we prove that any Clifford+T implementation of such a block encoding with error ε<121−1/nε<\frac{1}{2}\sqrt{1-1/n}ε<21​1−1/n​ requires at least 2n−22n-22n−2 T gates, even allowing arbitrary positive normalization and clean stabilizer ancillas. Taken together, these results establish the nearly optimal scaling of non-Clifford cost with the number of copies and uncover the fundamental resource requirements for coherent symmetry projection in quantum state purification.
Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.
Abstract The W state is a key resource for quantum communication and distributed quantum computing. Its entanglement survives the loss of any single qubit. Preparing the W state exactly is nevertheless hard in fault-tolerant architectures. The amplitude 1/√3 lies outside the ring Z[1/√2, i]. So no Clifford+T unitary can prepare the three-qubit W state exactly, and deterministic circuits must approximate the required rotation at a T-count that grows as log(1/ϵ). We present a heralded protocol that prepares the three-qubit W state exactly using Clifford gates and a single non-Clifford operation. A shallow Clifford circuit with two CNOT gates first prepares an equal superposition of |001⟩, |010⟩, |100⟩ and |111⟩. A logical-AND measurement on one ancilla then removes the |111⟩ component without disturbing the remaining coherent superposition. The protocol succeeds with probability 3/4, a failed attempt leaves the known product state |111⟩, and each attempt consumes four T gates or one |CCZ⟩ magic state. This gives an expected cost of about 5.33 T gates independent of target precision. We prove that some non-Clifford step is necessary, and by exhaustively enumerating all 315,057,600 six-qubit stabilizer tensors we show that no post-selected Clifford circuit with three or fewer T gates outputs the W state. Every heralded Clifford+T preparation of the W state therefore uses at least four T gates per successful run, and our protocol attains this bound. The protocol uses 6 to 19 times fewer T gates than gate synthesis at precisions between 10−3 and 10−10. We compare it with a deterministic circuit using an exact repeat-untilsuccess rotation, which achieves a slightly lower expected cost of about 4.67 T gates, and discuss implementation in modular architectures and extensions to N-qubit W states. Note on this version. This version replaces and corrects the first version of this preprint (“A Tcount Zero Protocol for Heralded W-state Preparation via Clifford-only Gates”). The claim there that the W state can be prepared with Clifford gates alone is incorrect: as shown here, some non-Clifford step is necessary, and at least four T gates are needed per successful run.
How much quantum storage must a hidden implementation retain when experimental observations leave its structure undetermined? This paper establishes exact minimum quantum-storage requirements across all implementations compatible with specified channel observations. The resource is the worst-input expected logarithm of retained quantum dimension across one controlled temporal cut, with unlimited classical records available at no cost. For the channel dimension measure introduced by Cope and Uola, the paper proves their suggested minimax equality relating minimum storage to output Schmidt measure and extends it to every nonempty compact convex set of compatible channels. One common input enforces the resource minimum across all compatible implementations. A finite optimal implementation exists, although an optimal entangled probe need not. For qubit channels, four measured coefficients determine an exact, attained minimum without assuming channel covariance or unitality. An explicit five-Kraus construction attains 99/169, while a separate analytical certificate proves that every compatible implementation must use nontrivial quantum storage with at least that probability on the same specified input. A second exact formula uses only two Pauli-transfer coefficients and yields a minimum storage requirement of 0.58 when both coefficients are jointly constrained to the interval [0.79, 0.81]. The paper also presents semidefinite optimization over compatible experimental uncertainty regions. The results require calibrated quantum inputs and outputs, concealed preparation labels, and accounting for every quantum carrier across the storage cut. They constrain storage resources without reconstructing the hidden implementation or certifying environmental non-Markovianity. Motivated by Shadow Theory’s source/readout distinction, the proofs use standard quantum mechanics and quantum-information mathematics. Version 1.1 includes complete proofs, explicit attaining constructions, worked examples, and discussion of experimental assumptions and limitations. No experimental data are reported.
For universal quantum computation, a major challenge to overcome for practical implementation is the large amount of resources required for fault-tolerant quantum information processing. An important aspect is implementing arbitrary unitary operators built from logical gates within the quantum error correction code. A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision by assembling sequences of logical gates chosen from a small set of universal gates that are fault-tolerantly performable while encoded in a quantum error-correction code. However, current procedures do not yet support individual assignment of base gate costs and many do not support extended sets of universal base gates. We analysed cost-optimal sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the canonical Clifford+ T set of base gates and compared them to when additionally including Z -rotations from higher orders of the Clifford hierarchy. Two approaches of assigning base gate costs were used. First, costs were reduced to T -counts by recursively applying a Z -rotation catalyst circuit. Second, costs were assigned as the average numbers of raw (i.e. physical level) magic states required to directly distil and implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to 54±3% when using the Z -rotation catalyst circuit approach and by up to 33±2% when using the magic state distillation approach. In addition, we investigated observed limitations of certain assignments of base gate costs by developing an analytic model to estimate the proportion of sets of Z -rotation gates from higher orders of the Clifford hierarchy that are found within sequences approximating random target gates.
Everettian quantum mechanics describes alternative histories within one evolving quantum state, while quantum Darwinism relates their accessibility to information retained in environmental records. I examine how finite record memory constrains the number of distinguishable histories and the organisation of their conditional ancestry. When d + 1 histories must each be decoded from a d-dimensional fragment with success d/(d + 1), the established discrimination optimum forces a regular-simplex geometry. Its conditional mixtures then determine exact ancestral edge costs and a joint criterion for the permissible topology, depth, total variation and largest step. In the three-history binary example, equally weighted labels decoded with success 2/3 require 61.6% greater minimum conditional variation in a qubit than in an optimally designed three-dimensional record. For six histories, minimising total variation and minimising the largest step select different genealogies. Quantitative stability estimates show that the additional constraint persists under sufficiently small departures from ideal decoding and weights. At this threshold, trace-distance contraction prevents a fixed channel acting only on an unrestricted optimum from compressing it into the smaller record at unchanged accuracy, although an explicit controlled preparation realises the alternative encoding. A von Neumann-inspired application distinguishes hereditary function, present configurations and retained mutation histories, and a comparison of finite and infinite counts separates these quantities from cosmological multiplicity. The resulting theory makes the limitations of environmental memory consequential for readable branching while keeping conditional variation distinct from physical rates of change. Its bounds apply to specified records and histories without assigning an absolute number of worlds since the universe’s beginning.