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.
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.
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, −φy, and a fixed offset −π/2. Direct calculation gives p0=21+21sin(φx−φy), so p0<1/2 indicates x<y for any strictly increasing encoding spanning less than π.
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)/(2t−1) under the stated range conditions. Hoeffding bounds give sampling cost O(sin−2dlog(1/δ)), where d=φx−φy. Multiplying gate angles by an integer r replaces d by rd without changing the circuit layout; correctness requires r∣d∣<π. An adaptive doubling schedule achieves O((1+log(1/∣d∣))log(L/δ)) shots with level budget L and sufficient resolution.
Evidence consists of analytic proofs and noiseless Qiskit simulations, including an 8×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 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((kn)) oracle calls, each of depth O(Δ+logn) 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.
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.
We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Its local penalties define only a cycle cover, so ground states may contain customer cycles disconnected from the depot. We construct a polynomial-size quadratic unconstrained binary optimization (QUBO) repair using capped single-commodity flow and prove connected, cost-optimal ground-state routings under explicit penalty assumptions. For N−1 customers and K nonempty routes, the unreduced encoding uses exactly ∣E∣(1+⌈log2(N−K+1)⌉) logical problem qubits. A reversible compute-phase-uncompute implementation evaluates the flow penalties in O(N2logN+Nlog2N) logical gates on a complete graph, using O(logN) reusable workspace and no product register. On complete loopless graphs, a position encoding that arranges all routes in one sequence separated by depot occurrences uses fewer problem qubits and written terms when the number of bits per flow register grows. Under the same reversible accounting model, the flow formulation admits a smaller logical-gate upper bound. Exact Hamiltonian and circuit audits and a benchmark of 1,200 cost matrices verify the formulation and quantify the connectivity gap. A 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits for a diagnostic N=4, K=1 counterexample. In the degree-only circuit, 78.05% of selected p=1 shots realize the invalid disconnected ground state; the reduced 14-qubit flow-augmented circuit yields no fully feasible sample. These device results characterize mapped Hamiltonians and compilation, not an asymptotic advantage in solving routing problems.