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

arXiv:2609.25262

A Quantum Phase-based Comparator

Alessandro Berti, Alessandro Poggiali

quant-phSubmitted Sep 21, 2026• Announced Sep 23, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum comparators decide the order of two operands. They rely on reversible logic acting on basis-encoded integers, so their width grows with the precision. We introduce the Quantum Phase-based Comparator (QPC), which compares two values carried in relative phases instead. The circuit places the two phases, entered with opposite signs, between a pair of Hadamard gates, and a fixed offset centers the interference, so that the probability of measuring zero falls below one half exactly when the first phase is the smaller. We give two implementations. With hard-coded values, the two values are written into the parameters of two phase gates, and the comparison costs one qubit and five gates. With the register-driven cascade, the values are drawn from two $t$-qubit registers through binary-weighted controlled-phase gates, at a cost of one qubit beyond the registers and depth linear in $t$; since the cascade induces each phase linearly from the register content, one circuit handles a superposition of operand pairs. The readout yields a biased coin rather than a definite bit, and we quantify the shots that a decision takes at a given phase separation. Scaling both phases by an integer widens the decision margin at no cost in width or depth, and an adaptive doubling schedule turns this amplification into a shot count logarithmic in the inverse separation.

AI Summary

The paper studies statistical order comparison when operands are supplied through phase gates or basis-encoded registers. Its primitive is a single-qubit interferometer with Hadamard gates surrounding phases $\varphi_x$, $-\varphi_y$, and a fixed offset $-\pi/2$. Direct calculation gives $p_0=\tfrac12+\tfrac12\sin(\varphi_x-\varphi_y)$, so $p_0<1/2$ indicates $x<y$ for any strictly increasing encoding spanning less than $\pi$. Hard-coded operands require one qubit and five gates. For two $t$-qubit registers, binary-weighted controlled-phase cascades use $2t+1$ qubits, $2t+3$ gates, and $O(t)$ depth, acting coherently on superpositions. For linear encoding over $[a,b]$, rounding preserves the order decision whenever $|x-y|>(b-a)/(2^t-1)$ under the stated range conditions. Hoeffding bounds give sampling cost $O(\sin^{-2}d\log(1/\delta))$, where $d=\varphi_x-\varphi_y$. Multiplying gate angles by an integer $r$ replaces $d$ by $rd$ without changing the circuit layout; correctness requires $r|d|<\pi$. An adaptive doubling schedule achieves $O((1+\log(1/|d|))\log(L/\delta))$ shots with level budget $L$ and sufficient resolution. Evidence consists of analytic proofs and noiseless Qiskit simulations, including an $8\times8$ image-thresholding demonstration using 22 qubits. The output is a biased flag, not an exact comparison bit. Adaptive readout of superpositions requires branch-resolved sampling, with costs depending on branch weights. Arbitrary-angle synthesis and noise are not evaluated. The amplitude-estimation baseline uses a different input model; exact reversible comparators have comparable register width and return definite bits.

Some signs of AI-generated textOverclaimsUnclear noveltyStrong assumptionsPossible error

Error found: The abstract omits the phase-range restriction needed for its order rule, although the theorem correctly requires |φx−φy|<π. Phase powering increases the margin only conditionally and is gate-count-free only under the paper's adjustable-angle access model, qualifications supplied in the body but missing from the abstract's broad formulation. The proved adaptive schedule costs O(log(1/u) log log(1/u)) shots at fixed confidence when its resolution budget grows to cover arbitrarily small separations, rather than the unqualified logarithmic scaling advertised. Section 6.1 incorrectly invokes the adaptive corollary's stopping-before-wrapping guarantee for experimental parameters and a threshold rule that do not satisfy that corollary's assumptions. The adaptive example labels level 3 'below threshold' even though its true margin is approximately 0.19471 and the stated threshold is approximately 0.17678.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum comparator circuit on superconducting quantum computer

Naphan Benchasattabuse

In this thesis, we present an optimised quantum comparator circuit based on Cuccaro's ripple-carry quantum adder using relative phase techniques from Maslov's multiple control Toffoli optimisation. We extend the cost function from simply counting C-Not and Toffoli gate to Qiskit cost which defines arbitrary single qubit gate cost as unity and C-Not as the only two qubit gate cost as ten. We report the comparison result between our comparator circuit with previous comparator circuits from literature using optimal Toffoli implementation with Qiskit cost, C-Not count, and circuit depth. We also report our experiment of implementing a two-bit comparator on IBM QX devices.

•Jan 1, 2019•1 citation

A Framework for Quantum Circuit Optimization: Comparators as a Case Study

Francisco José Orts, Rodrigo Gil-Merino

Qubits are the minimum unit of information in quantum computing. As current quantum devices have a very limited number of available qubits, finding circuits that optimize their use is crucial for this computing paradigm. Optimizing the qubits needed to implement a quantum circuit is not trivial, as these circuits have important restrictions such as the impossibility of copying values or the requirement that the computation done in them must always be reversible. This paper presents a framework for optimizing circuits for quantum computing. The framework is able to obtain, given a quantum circuit, an equivalent one that is more efficient in terms of number of qubits. In particular, the framework has applicability in quantum circuits dedicated to arithmetic operations such as addition or multiplication. As a representative case study, it is applied to a reversible comparator circuit, obtaining a design that reduces the number of qubits and controlled gates compared to other reversible comparators reported in the recent literature. As part of the work, a public repository is included with the necessary code to simplify any other circuit.

IEEE Transactions on Computers•Dec 12, 2025•0 citations

Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

Payman Kazemikhah, Ali Hadizadeh Moghadam, Hossein Aghababa

Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published $k$-clique circuits have depth quadratic in the number $n$ of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact $k$-clique oracle, whose depth and width are linear in $n$, within a logarithmic factor of a depth--width lower bound. Our central result is a $k$-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in $n$ for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is $-1$ for cliques and, as we prove, at most $5/8$ in modulus otherwise, a tight bound that tends to $1/2$ as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a $k$-clique with $O(\sqrt{\binom nk})$ oracle calls, each of depth $O(Δ+\log n)$ for maximum degree $Δ$. The guarantee holds for two or more estimation registers; exact simulations on $312$ induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.

arXiv:2308.16827•Aug 31, 2023•1 citation

The survivor count of a binary linear code: exact structure, counting complexity, and the bridge to Clifford+T circuits

N. Podgorski

To predict what a quantum computer will output you have to work out an astronomical sum, and almost every term in it cancels to nothing. This work counts how many actually survive, and shows that number is out of reach of the standard tools: not the Tutte polynomial, not the usual weight counts, not the usual recursions. A binary linear code is a set of bit strings closed under bitwise addition — the object behind error-correcting codes. This paper studies a counting quantity attached to such a code, its survivor count. Where it comes from. Take a quantum circuit built from Clifford gates and T gates and ask for the expected value of its output. That expectation is a signed sum of exponentially many terms — quadratic Gauss sums over the two-element field — indexed by the codewords of a binary linear code. What that sum comes to is a well-studied quantity. This paper asks a different question about the same sum: not what it adds up to, but how many of its terms are really there. The number that survive is the survivor count of the code. What was already known, and what is taken up here. Whether one individual term survives is classical: a quadratic Gauss sum vanishes unless its form is trivial on the radical of its polar form, and is otherwise a power of two carrying the Arf sign. The weight attached to a single support is published as well, as the local isotropic-nullity weight of Bouchet's isotropic systems and of the restricted Tutte–Martin polynomial; the paper treats it as background rather than as a result of its own. What the paper takes up is the whole family at once. The census runs over all 2k codewords of a code, and the questions asked are what determines that total, what exact evaluation costs, which parameters and moduli buy an algorithm, and how far into the planar case each side reaches. What the paper proves. An exact criterion, and a closed form. The class sum at a support vanishes unless a certain half-weight form vanishes on a radical; where it does not vanish, the survivors are counted exactly by a power of two read off the dimensions of the code. One parity obstruction can remove them all. Consequently the survivor count depends only on the code's binary matroid. Separations. It is determined by none of the following: the Tutte polynomial; the cycle and cut weight enumerators taken together on planar graphs; the local marginals. It is not invariant under duality, and it obeys no constant-coefficient deletion–contraction recursion. The standard machinery that classifies graph and matroid invariants therefore does not reach it, and every line drawn below between easy and hard is drawn from the definition instead. A complexity map. Exact evaluation is #P-complete under deterministic polynomial-time Turing reductions, both on explicit generators and on graph cycle codes, and stays hard on four restricted graph families, on linear complementary dual codes, and at each fixed hull dimension. It is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes, and modulo 2, 3 and 6. Planar graphs. An exact algorithm running in time 2O(√n log n), conditional on three imported constructors, together with a #P-hardness statement conditional on one named planar Tutte evaluation being #P-hard. A bridge to quantum circuits, in both directions. Every Clifford+T circuit compiles to a single code and a single integer h whose output expectation is exactly (A + B√2)/2h+1, an identity holding exactly in the ring Z[√2], where (A,B) is that code's mod-8 weight census. Separately, a reverse construction makes the sign of such a bias hard for PromiseBQP at an exponentially small threshold, while at inverse-polynomial thresholds the same sign is decided classically with bounded error. Scope, and what is not claimed. Every statement carries exactly the status its proof supports and never a stronger one. Results resting on an unproved hypothesis carry that hypothesis at the head of their own statement, and no hypothesis is discharged anywhere in the paper. Nothing here claims, implies or denies any equality or separation of complexity classes. Where a comparison with the literature was not made, the paper says so at the statement it touches; nothing here asserts priority. Supplementary material. The consolidated record, and the proof files named in the paper's appendix, are deposited separately at doi:10.5281/zenodo.22804078. Abstract, as printed in the paper A Clifford+T circuit's output expectation is a signed sum of quadratic Gauss sums over the codewords of a binary linear code; counted here is how many survive. For C in F_2^m, let K_F be the dual subcode supported in a codeword F and R_F its radical: the survivor count S(C) counts, over all F, the cosets of K_F in the even-weight subspace on F with nonzero Gauss sum. An exact criterion is proved: the class sum at F vanishes unless the half-weight form twisted by the class representative s vanishes on R_F, and survivors at nonzero F number 2^(|F|-1-dim K_F-dim R_F+[F in the dual]), or none under a parity obstruction. So S is a binary-matroid invariant determined by none of the Tutte polynomial, the cycle and cut weight enumerators together on planar graphs, or the local marginals, not duality-invariant, and obeying no constant-coefficient deletion-contraction recursion. Exact evaluation is #P-complete under polynomial-time Turing reductions, and stays hard on four restricted graph families, on linear complementary dual codes and at each fixed hull dimension; it is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes and modulo 2, 3, 6. For planar graphs an exact 2^(O(sqrt(n) log n)) algorithm is given, conditional on three imported constructors, with hardness conditional on one named planar Tutte evaluation being #P-hard. Every such circuit compiles to one code and an integer h with output expectation exactly (A+B sqrt 2)/2^(h+1) in Z[sqrt 2], for (A,B) that code's mod-8 weight census; a reverse construction makes that sign PromiseBQP-hard at an exponentially small threshold, while inverse-polynomial ones are decided classically with bounded error. No complexity-class equality or separation is claimed or denied.

•Sep 17, 2026•0 citations

A Quantum Probabilistic Comparator: Circuit Implementation

Linh Nguyen, Zhenhua Jiang

Decision making in stochastic autonomous systems, which considers uncertainty of many factors, is always a challenge. The problem can typically be addressed by probabilistic methods such as approximate stochastic optimization or Monte Carlo (MC) simulation. The potential solution may usually be constrained by the system's computing power, due to the size of the probabilistic problem. This paper aims to present and implement a quantum probabilistic comparison (QPC) algorithm that can help to find a desired solution or make decision between two random variables under uncertainty. This approach takes advantage of quantum computing to perform parallel comparison and fast calculation of the probability of matched state vectors. In the presented scheme, two random variables have different values (e.g., 2, 4, 8, or more values) and different probability distributions. The data of the variables are encoded to the basis states of the corresponding qubits. The quantum probabilistic comparator is used to make up the quantum output matrix that stores the comparison solutions as well as their probability probabilities. Moreover, unlike the existing quantum comparator algorithm, which uses bit string comparison approaches, the proposed probabilistic comparator is not only comparing the basis state, but also accumulating the outcome's probabilities. The calculation results of the quantum probabilistic comparator circuit are compared with those from classical computation and quantum circuit simulation as well as on an IBM quantum computer, for analysis and verification.

IEEE National Aerospace and Electronics Conference (NAECON)•Aug 28, 2023•2 citations

Efficient Block Encoding of Structured Hamiltonians by Separating Where and What

Alessandro Summer, François Jamet

In fault-tolerant block encodings of structured Hamiltonians, the support geometry can set how the non-Clifford cost of SELECT scales with the system size, however many operators act on each support. We construct permute-act-unpermute circuits: a CSWAP network fixed by this geometry brings a selected support to a fixed target register, a shared local circuit acts there, and the permutation is undone. The operators add only an $XZ$ mask on this register, at a cost independent of the system size, and one query can mix several support geometries. For two-site supports, we establish and attain the minimum CSWAP count within address-controlled networks of site transpositions. Compiled for Pauli terms, these circuits use $8\mathrm{S}N+o(N)$ $T$ gates with $O(\log N)$ permutation work qubits, where $N$ is the number of system qubits and $\mathrm{S}$ is determined by the support geometry, with $\mathrm{S}=1$ for nearest-neighbour interactions and $\mathrm{S}=3/2$ for all-to-all pairs; in both cases the correction is $O(\log N)$. We also introduce a bridged CSWAP, which remembers the logical value of its temporary AND across the target action and repairs it from the prepared labels, so that the inverse CSWAP undoes the exchange without recomputing the value. When the repair is Clifford, it halves the $T$ count of a matched forward-inverse CSWAP pair at the cost of one retained work qubit. For a Heisenberg ring, the complete block-encoding query reduces the $T$ count by a factor approaching $3$ as the system size grows, relative to flat and product-wise Pauli walks. For a five-orbital Anderson impurity model, which combines nearest-neighbour and all-to-all support geometries, the reduction is about $1.7$ at large bath sizes, relative to the cheapest of three comparators, each built from the methods of the references it follows.

quant-pharXiv:2610.03686•Oct 5, 2026•2 citations
Quantum comparators decide the order of two operands. They rely on reversible logic acting on basis-encoded integers, so their width grows with the precision. We introduce the Quantum Phase-based Comparator (QPC), which compares two values carried in relative phases instead. The circuit places the two phases, entered with opposite signs, between a pair of Hadamard gates, and a fixed offset centers the interference, so that the probability of measuring zero falls below one half exactly when the first phase is the smaller. We give two implementations. With hard-coded values, the two values are written into the parameters of two phase gates, and the comparison costs one qubit and five gates. With the register-driven cascade, the values are drawn from two ttt-qubit registers through binary-weighted controlled-phase gates, at a cost of one qubit beyond the registers and depth linear in ttt; since the cascade induces each phase linearly from the register content, one circuit handles a superposition of operand pairs. The readout yields a biased coin rather than a definite bit, and we quantify the shots that a decision takes at a given phase separation. Scaling both phases by an integer widens the decision margin at no cost in width or depth, and an adaptive doubling schedule turns this amplification into a shot count logarithmic in the inverse separation.
The paper studies statistical order comparison when operands are supplied through phase gates or basis-encoded registers. Its primitive is a single-qubit interferometer with Hadamard gates surrounding phases φx\varphi_xφx​, −φy-\varphi_y−φy​, and a fixed offset −π/2-\pi/2−π/2. Direct calculation gives p0=12+12sin⁡(φx−φy)p_0=\tfrac12+\tfrac12\sin(\varphi_x-\varphi_y)p0​=21​+21​sin(φx​−φy​), so p0<1/2p_0<1/2p0​<1/2 indicates x<yx<yx<y for any strictly increasing encoding spanning less than π\piπ.
Hard-coded operands require one qubit and five gates. For two ttt-qubit registers, binary-weighted controlled-phase cascades use 2t+12t+12t+1 qubits, 2t+32t+32t+3 gates, and O(t)O(t)O(t) depth, acting coherently on superpositions. For linear encoding over [a,b][a,b][a,b], rounding preserves the order decision whenever ∣x−y∣>(b−a)/(2t−1)|x-y|>(b-a)/(2^t-1)∣x−y∣>(b−a)/(2t−1) under the stated range conditions. Hoeffding bounds give sampling cost O(sin⁡−2dlog⁡(1/δ))O(\sin^{-2}d\log(1/\delta))O(sin−2dlog(1/δ)), where d=φx−φyd=\varphi_x-\varphi_yd=φx​−φy​. Multiplying gate angles by an integer rrr replaces ddd by rdrdrd without changing the circuit layout; correctness requires r∣d∣<πr|d|<\pir∣d∣<π. An adaptive doubling schedule achieves O((1+log⁡(1/∣d∣))log⁡(L/δ))O((1+\log(1/|d|))\log(L/\delta))O((1+log(1/∣d∣))log(L/δ)) shots with level budget LLL and sufficient resolution.
Evidence consists of analytic proofs and noiseless Qiskit simulations, including an 8×88\times88×8 image-thresholding demonstration using 22 qubits. The output is a biased flag, not an exact comparison bit. Adaptive readout of superpositions requires branch-resolved sampling, with costs depending on branch weights. Arbitrary-angle synthesis and noise are not evaluated. The amplitude-estimation baseline uses a different input model; exact reversible comparators have comparable register width and return definite bits.
In this thesis, we present an optimised quantum comparator circuit based on Cuccaro's ripple-carry quantum adder using relative phase techniques from Maslov's multiple control Toffoli optimisation. We extend the cost function from simply counting C-Not and Toffoli gate to Qiskit cost which defines arbitrary single qubit gate cost as unity and C-Not as the only two qubit gate cost as ten. We report the comparison result between our comparator circuit with previous comparator circuits from literature using optimal Toffoli implementation with Qiskit cost, C-Not count, and circuit depth. We also report our experiment of implementing a two-bit comparator on IBM QX devices.
Qubits are the minimum unit of information in quantum computing. As current quantum devices have a very limited number of available qubits, finding circuits that optimize their use is crucial for this computing paradigm. Optimizing the qubits needed to implement a quantum circuit is not trivial, as these circuits have important restrictions such as the impossibility of copying values or the requirement that the computation done in them must always be reversible. This paper presents a framework for optimizing circuits for quantum computing. The framework is able to obtain, given a quantum circuit, an equivalent one that is more efficient in terms of number of qubits. In particular, the framework has applicability in quantum circuits dedicated to arithmetic operations such as addition or multiplication. As a representative case study, it is applied to a reversible comparator circuit, obtaining a design that reduces the number of qubits and controlled gates compared to other reversible comparators reported in the recent literature. As part of the work, a public repository is included with the necessary code to simplify any other circuit.
Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published kkk-clique circuits have depth quadratic in the number nnn of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact kkk-clique oracle, whose depth and width are linear in nnn, within a logarithmic factor of a depth--width lower bound. Our central result is a kkk-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in nnn for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is −1-1−1 for cliques and, as we prove, at most 5/85/85/8 in modulus otherwise, a tight bound that tends to 1/21/21/2 as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a kkk-clique with O((nk))O(\sqrt{\binom nk})O((kn​)​) oracle calls, each of depth O(Δ+log⁡n)O(Δ+\log n)O(Δ+logn) for maximum degree ΔΔΔ. The guarantee holds for two or more estimation registers; exact simulations on 312312312 induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.
To predict what a quantum computer will output you have to work out an astronomical sum, and almost every term in it cancels to nothing. This work counts how many actually survive, and shows that number is out of reach of the standard tools: not the Tutte polynomial, not the usual weight counts, not the usual recursions. A binary linear code is a set of bit strings closed under bitwise addition — the object behind error-correcting codes. This paper studies a counting quantity attached to such a code, its survivor count. Where it comes from. Take a quantum circuit built from Clifford gates and T gates and ask for the expected value of its output. That expectation is a signed sum of exponentially many terms — quadratic Gauss sums over the two-element field — indexed by the codewords of a binary linear code. What that sum comes to is a well-studied quantity. This paper asks a different question about the same sum: not what it adds up to, but how many of its terms are really there. The number that survive is the survivor count of the code. What was already known, and what is taken up here. Whether one individual term survives is classical: a quadratic Gauss sum vanishes unless its form is trivial on the radical of its polar form, and is otherwise a power of two carrying the Arf sign. The weight attached to a single support is published as well, as the local isotropic-nullity weight of Bouchet's isotropic systems and of the restricted Tutte–Martin polynomial; the paper treats it as background rather than as a result of its own. What the paper takes up is the whole family at once. The census runs over all 2k codewords of a code, and the questions asked are what determines that total, what exact evaluation costs, which parameters and moduli buy an algorithm, and how far into the planar case each side reaches. What the paper proves. An exact criterion, and a closed form. The class sum at a support vanishes unless a certain half-weight form vanishes on a radical; where it does not vanish, the survivors are counted exactly by a power of two read off the dimensions of the code. One parity obstruction can remove them all. Consequently the survivor count depends only on the code's binary matroid. Separations. It is determined by none of the following: the Tutte polynomial; the cycle and cut weight enumerators taken together on planar graphs; the local marginals. It is not invariant under duality, and it obeys no constant-coefficient deletion–contraction recursion. The standard machinery that classifies graph and matroid invariants therefore does not reach it, and every line drawn below between easy and hard is drawn from the definition instead. A complexity map. Exact evaluation is #P-complete under deterministic polynomial-time Turing reductions, both on explicit generators and on graph cycle codes, and stays hard on four restricted graph families, on linear complementary dual codes, and at each fixed hull dimension. It is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes, and modulo 2, 3 and 6. Planar graphs. An exact algorithm running in time 2O(√n log n), conditional on three imported constructors, together with a #P-hardness statement conditional on one named planar Tutte evaluation being #P-hard. A bridge to quantum circuits, in both directions. Every Clifford+T circuit compiles to a single code and a single integer h whose output expectation is exactly (A + B√2)/2h+1, an identity holding exactly in the ring Z[√2], where (A,B) is that code's mod-8 weight census. Separately, a reverse construction makes the sign of such a bias hard for PromiseBQP at an exponentially small threshold, while at inverse-polynomial thresholds the same sign is decided classically with bounded error. Scope, and what is not claimed. Every statement carries exactly the status its proof supports and never a stronger one. Results resting on an unproved hypothesis carry that hypothesis at the head of their own statement, and no hypothesis is discharged anywhere in the paper. Nothing here claims, implies or denies any equality or separation of complexity classes. Where a comparison with the literature was not made, the paper says so at the statement it touches; nothing here asserts priority. Supplementary material. The consolidated record, and the proof files named in the paper's appendix, are deposited separately at doi:10.5281/zenodo.22804078. Abstract, as printed in the paper A Clifford+T circuit's output expectation is a signed sum of quadratic Gauss sums over the codewords of a binary linear code; counted here is how many survive. For C in F_2^m, let K_F be the dual subcode supported in a codeword F and R_F its radical: the survivor count S(C) counts, over all F, the cosets of K_F in the even-weight subspace on F with nonzero Gauss sum. An exact criterion is proved: the class sum at F vanishes unless the half-weight form twisted by the class representative s vanishes on R_F, and survivors at nonzero F number 2^(|F|-1-dim K_F-dim R_F+[F in the dual]), or none under a parity obstruction. So S is a binary-matroid invariant determined by none of the Tutte polynomial, the cycle and cut weight enumerators together on planar graphs, or the local marginals, not duality-invariant, and obeying no constant-coefficient deletion-contraction recursion. Exact evaluation is #P-complete under polynomial-time Turing reductions, and stays hard on four restricted graph families, on linear complementary dual codes and at each fixed hull dimension; it is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes and modulo 2, 3, 6. For planar graphs an exact 2^(O(sqrt(n) log n)) algorithm is given, conditional on three imported constructors, with hardness conditional on one named planar Tutte evaluation being #P-hard. Every such circuit compiles to one code and an integer h with output expectation exactly (A+B sqrt 2)/2^(h+1) in Z[sqrt 2], for (A,B) that code's mod-8 weight census; a reverse construction makes that sign PromiseBQP-hard at an exponentially small threshold, while inverse-polynomial ones are decided classically with bounded error. No complexity-class equality or separation is claimed or denied.
Decision making in stochastic autonomous systems, which considers uncertainty of many factors, is always a challenge. The problem can typically be addressed by probabilistic methods such as approximate stochastic optimization or Monte Carlo (MC) simulation. The potential solution may usually be constrained by the system's computing power, due to the size of the probabilistic problem. This paper aims to present and implement a quantum probabilistic comparison (QPC) algorithm that can help to find a desired solution or make decision between two random variables under uncertainty. This approach takes advantage of quantum computing to perform parallel comparison and fast calculation of the probability of matched state vectors. In the presented scheme, two random variables have different values (e.g., 2, 4, 8, or more values) and different probability distributions. The data of the variables are encoded to the basis states of the corresponding qubits. The quantum probabilistic comparator is used to make up the quantum output matrix that stores the comparison solutions as well as their probability probabilities. Moreover, unlike the existing quantum comparator algorithm, which uses bit string comparison approaches, the proposed probabilistic comparator is not only comparing the basis state, but also accumulating the outcome's probabilities. The calculation results of the quantum probabilistic comparator circuit are compared with those from classical computation and quantum circuit simulation as well as on an IBM quantum computer, for analysis and verification.
In fault-tolerant block encodings of structured Hamiltonians, the support geometry can set how the non-Clifford cost of SELECT scales with the system size, however many operators act on each support. We construct permute-act-unpermute circuits: a CSWAP network fixed by this geometry brings a selected support to a fixed target register, a shared local circuit acts there, and the permutation is undone. The operators add only an XZXZXZ mask on this register, at a cost independent of the system size, and one query can mix several support geometries. For two-site supports, we establish and attain the minimum CSWAP count within address-controlled networks of site transpositions. Compiled for Pauli terms, these circuits use 8SN+o(N)8\mathrm{S}N+o(N)8SN+o(N) TTT gates with O(log⁡N)O(\log N)O(logN) permutation work qubits, where NNN is the number of system qubits and S\mathrm{S}S is determined by the support geometry, with S=1\mathrm{S}=1S=1 for nearest-neighbour interactions and S=3/2\mathrm{S}=3/2S=3/2 for all-to-all pairs; in both cases the correction is O(log⁡N)O(\log N)O(logN). We also introduce a bridged CSWAP, which remembers the logical value of its temporary AND across the target action and repairs it from the prepared labels, so that the inverse CSWAP undoes the exchange without recomputing the value. When the repair is Clifford, it halves the TTT count of a matched forward-inverse CSWAP pair at the cost of one retained work qubit. For a Heisenberg ring, the complete block-encoding query reduces the TTT count by a factor approaching 333 as the system size grows, relative to flat and product-wise Pauli walks. For a five-orbital Anderson impurity model, which combines nearest-neighbour and all-to-all support geometries, the reduction is about 1.71.71.7 at large bath sizes, relative to the cheapest of three comparators, each built from the methods of the references it follows.