Introduction
Combinatorial optimization problems (COP) underpin modern logistics, manufacturing, finance, and drug discovery; and it surfaces throughout artificial intelligence and machinelearning workflows [1 , 2 , 3 , 4 ] . Classical methods like branch–and–bound and cutting planes [2 , 5 , 6 ] excel when they exploit problem structure. In contrast, many near-term quantum approaches—notably QAOA [7 ] and its variants [8 , 9 , 10 ] —tend to explore the full Hilbert space in search of the (near) optimal solution(s), paying in measurement cost [11 , 12 ] , depth [11 , 12 ] , and barren plateaus [13 ] . A growing line of work mitigates this by encoding directly into symmetry-rich feasible subspaces and using feasibility-preserving mixers [14 , 15 , 16 , 17 , 18 , 19 ] . In this work we study Constraint–Enhanced Quantum Approximate Optimization Algorithm (CE–QAOA), a shallow, constraint-aware ansatz that natively operates on a block one-hot manifold. Our circuit constructions are based on an ancilla-free, depth-optimal encoder that prepares a block W n W_n W n state using exactly n − 1 n-1 n − 1 excitation preserving two qubit gates, and a two-local block–XY mixer that preserves the manifold.[14 ] The properties arising from these circuit primitives allow us to make contact with low-order moment analysis of random quantum circuits[20 ] in the encoded subspace and to subsequently study the emergence of approximate unitary t − t- t − designs.
Why do unitary t t t -designs matter? In the context of variational quantum circuits, unitary designs are a principled proxy for expressivity , anticoncentration , and typical-case trainability [20 ] . Recall that a unitary t t t -design reproduces Haar moments up to degree t t t . Thus any degree-≤ t \le t ≤ t observable (e.g., overlaps, energies, and many gradient statistics) computed under the design agrees with the Haar baseline up to ε \varepsilon ε [20 ] . Secondly, for t = 2 t = 2 t = 2 , 2-designs suggests an instance-agnostic typical-case behaviour because second moments are insensitive to the fine details of the cost landscape. From the “landscape information” viewpoint [21 ] , matching Haar second moments ensures that a nontrivial amount of task-relevant variance survives at shallow depth on the encoded space, which increases the effective information capacity of the ansatz [21 , 22 ] .
Our circuit design inherits from prior work in Refs. [14 , 23 ] . Here we leverage additional problem specific structures through problem-algorithm codesign to capture a broad class of COPs (TSP/ATSP, QAP, CVRP, etc) via block one-hot encodings and shared constraint properties. Consequently, we propose a unifying kernel in Def. 1. Within this kernel, a block-permutation twirl yields a unitary 1-design on the encoded space, reproducing the Haar baseline E [ ∣ ⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 ] = 1 / D \mathbb{E}\left[|\langle x|U|\phi\rangle|^2\right] = 1/D E [ ∣ ⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 ] = 1/ D and a corresponding existence theorem for any target basis vector x ⋆ x^\star x ⋆ (and thus for the optimum) in Thm. 13 and Cor. 16. Algorithmically, we introduce the the Polynomial time Hybrid Quantum-Classical Solver (PHQC) which wraps constant-depth quantum sampling over a coarse parameter grid with a deterministic classical checker that identifies the best sampled solutions, operationalizing these t t t -design bounds. PHQC identifies the optimal solution if it is sampled at least once.
Our running examples are derived from the Travelling Salesman Problem (TSP) where the n 2 n^2 n 2 qubits are imagined to be arranged in n n n blocks of size n n n and the double one-hot constraint restricts to a fixed-Hamming-weight manifold containing only n ! n! n ! basis states out of the encoded n n n^n n n encoded basis vectors and 2 n 2 2^{n^2} 2 n 2 vectors in the ambient Hilbert space [24 ] . Similar one-hot encoded problems arise naturally for assignment problems [25 ] , matching problems [26 ] , vehicle routing problems [3 ] , graph coloring problems [24 ] and the recently introduced shared transportation framework [27 ] . CE–QAOA exploits this structure at the encoder, mixer layers, phase layers, and classical feasibility checker; extending problem–algorithm co-design from quantum to classical stage [28 , 29 ] . The advertised quantum advantage comes from direct utilization of problem structures at the classical and quantum levels of the algorithm.
We present noiseless circuit simulation results for TSP instances ranging from 4 to 10 locations drawn from the QOPTLib benchmark problems[30 ] . We demonstrate that PHQC recovered the optimal solution in all instances considered while dramatically reducing the shot cost to a polynomial O ( n k ) O(n^k) O ( n k ) at depth p = 1 p = 1 p = 1 as reported in Table 1 . All plots presented in the following can be reproduced as demonstrated in [31 ] .
Table 1. Single-layer CE-QAOA sampling with design-based angles and shot budget S = 10 n 3 − 5 S=10n^{3-5} S = 10 n 3 − 5 used to recover the global optimum. For a fair comparison, we assume a classical sampler with access to the block one-hot space so that the classical shot cost formula S c l = Θ ( n m − 1 log ( 1 / δ ) ) S_{\mathrm{cl}}=\Theta(n^{m-1}\log(1/\delta)) S cl = Θ ( n m − 1 log ( 1/ δ )) holds. We set log ( 1 / δ ) = 10 \log(1/\delta)=10 log ( 1/ δ ) = 10 for both quantum and classical models and n r n^r n r refers to the ratio in Eq. (15) .
Relation to Prior Work
Recently, Smith–Miles et al. [32 ] surveyed the obstacles to near-term quantum advantage on TSP—including resource inflation from generic encodings (e.g., QUBO), feasibility handling, noise/optimizer pathologies, and inconsistent benchmarking against strong classical solvers—and argue for structure-exploiting formulations and transparent, reproducible evaluations. Our CE–QAOA/PHQC approach aligns with this perspective but differs in emphasis because we treat global constraints as useful structure within an encoded manifold. Our formalism inherits from the preexisting body of work in the alternating-operator literature (often called QAOA+) which develops mixers that commute with, or otherwise preserve, constraint projectors—e.g., one-hot, ring mixers, and null-swaps [14 , 33 ] . For routing families (e.g., CVRP), feasibility is frequently enforced via Grover-style oracles [19 , 16 , 34 ] , which introduce oracle/ancilla overhead and reflection-based subroutines. In contrast, our kernel uses a two-local, ancilla-free block–XY mixer that preserves all blockwise one-hot constraints, acts entirely within the encoded manifold, and is normalized to have a constant spectral gap on the one-excitation sector (Prop. 7). The initial state is the block-W product [35 ] prepared by an ancilla-free, depth-optimal cascade (Thm. 4 ), making the mixer’s top eigenvector the initial state. Our mixer design ensures invariance (excitation conservation) and block factorization, enabling quditization H M ( b ) ↦ A ( K n ) H_{M}^{(b)} \mapsto A(K_n) H M ( b ) ↦ A ( K n ) [14 ] and explicit control of norms and gaps at the encoded per block level. This normalization is used quantitatively in our mixing/expressivity arguments and avoids hidden n n n -dependent angles that can plague unnormalized XY implementations.
Unlike prior feasibility-preserving approaches (e.g. QAOA+ [14 , 16 , 34 ] ), our kernel explicitly requires that the constraints be exchangeable under block permutations S m S_m S m and symbol relabelings S n S_n S n . This symmetry is a co-design choice that is enforced at the modeling level and then exploited algorithmically. Two consequences are central to our analysis: (i) H p e n H_{\mathrm{pen}} H pen is invariant under S m × S n S_m \times S_n S m × S n , so every penalty level set L t = { x : H p e n ( x ) : = ⟨ x ∣ H p e n ∣ x ⟩ = t } L_t = \{x : H_{\mathrm{pen}}(x) := \langle x \mid H_{\mathrm{pen}} \mid x \rangle= t\} L t = { x : H pen ( x ) := ⟨ x ∣ H pen ∣ x ⟩ = t } (in particular L 0 L_0 L 0 ) is preserved setwise; and (ii) a block-permutation twirl acts transitively on the encoded basis and yields an exact unitary 1-design on H O H \mathcal{H}_{\mathrm{OH}} H OH (Lemma 15 ). This exact first-moment identity directly powers our existence guarantee for the optimal basis vector x ⋆ x^\star x ⋆ (Cor. 16). This symmetry-driven 1-design baseline, and the resulting existence results, differentiate our co-designed kernel from prior feasibility-preserving approaches.
Although our kernel uses familiar primitives, here we study them under the lens of norms, spectral properties, and typical case behaviors. By systematic use of low-order moment methods (L 1 L_1 L 1 , L 2 L_2 L 2 ) together with symmetry and twirling, we expose and utilize: (i) Lie controllability and approximate universality within the one-excitation sectors induced by the block–XY mixer; (ii) ε \varepsilon ε -approximate unitary 2-designs at shallow depth arising from per-block design plus diagonal entanglers; (iii) exponentially fast mixing and anticoncentration on the encoded manifold; and (iv) expressivity that translates into provable lower tails at the c / D c/D c / D scale. Where D D D is the encoded dimension and c > 0 c > 0 c > 0 from Thm. 13 . To our knowledge, prior feasibility-preserving or domain-specific QAOA variants do not provide universal, instance-agnostic guarantees of this kind.
Our analyses remain complementary to recent work on landscape information content [21 ] ; and analysis of energy/gradient landscapes and alternating-operator structure [22 ] . Our ap approach equally remains orthogonal to warm-start schedules [36 , 35 ] . Warm starts can yield strong numerics but provide limited worst-case control and sometimes require non-eigen initializations of the mixer, violating the adiabatic protocol and limiting performance [37 ] . We avoid classical initialization completely and focus on provable algorithmic performance.
Codesign and Circuit Primitives for CE-QAOA
Problem-Algorithm Codesign
Our goal is to identify potential opportunities for provable algorithmic enhancements by taking explicit advantage of problem structure . This aligns with the broader co-design perspective in quantum computing, where algorithms and platforms are jointly tailored to application constraints and device characteristics [28 , 29 ] . Here, however, we omit hardware considerations and focus on problem-algorithm co-design. We look beyond feasibility-preserving ansätze and mixers [14 , 38 , 15 , 19 , 34 ] and impose additional symmetry on the constraint structure consistent with the various problem classes, bringing them under a single kernel defined in Def. 1. As a consequence, performance bounds obtained propagate across a broad class of COPs with minimal tweaks. The definition below fixes what it means to be “in the kernel” and will be the used henceforth for all results that follow.
Definition 1 (CE–QAOA kernel). An optimization instance I I I belongs to the CE–QAOA kernel if there exist integers n , m ∈ N n,m \in\mathbb{N} n , m ∈ N and the one-hot encoder E 1 h o t E_{\mathrm{1hot}} E 1hot that initializes the dynamics in the fixed–Hamming–weight space
H O H = ( H 1 ) ⊗ m , H 1 = span { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩ } (one excitation per block). \mathcal{H}_{\mathrm{OH}} = \left(\mathcal{H}_1\right)^{\otimes m}, \qquad\mathcal{H}_1 = \operatorname{span}\{\lvert e_0\rangle,\ldots,\lvert e_{n-1}\rangle\}\quad\text{(one excitation per block).} H OH = ( H 1 ) ⊗ m , H 1 = span {∣ e 0 ⟩ , … , ∣ e n − 1 ⟩} (one excitation per block). The problem Hamiltonian splits as
H C = H p e n + H o b j , H_C = H_{\mathrm{pen}} + H_{\mathrm{obj}}, H C = H pen + H obj , Where H o b j H_{\mathrm{obj}} H obj is the Ising Hamiltonian representing the objective and only needs to be diagonal in the computational basis. H p e n H_{\mathrm{pen}} H pen is the penalty Hamiltonian and enjoys the symmetries specified in (a) and (b) in addition to being diagonal in the computational basis.
(a) Penalty structure. H p e n H_{\mathrm{pen}} H pen is a sum of squared affine one-hot/degree/capacity penalties (optionally plus linear forbids) with integer coefficients bounded by poly ( n ) \operatorname{poly}(n) poly ( n ) . Consequently, spec ( H p e n ) ⊆ { 0 , 1 , … , t max } \operatorname{spec}(H_{\mathrm{pen}}) \subseteq\{0,1,\ldots,t_{\max}\} spec ( H pen ) ⊆ { 0 , 1 , … , t m a x } with t max = O ( m ) = poly ( n ) t_{\max} = O(m) = \operatorname{poly}(n) t m a x = O ( m ) = poly ( n ) .
(b) Pattern symmetry. H p e n H_{\mathrm{pen}} H pen is invariant under (i) block permutations S m S_m S m and (ii) global symbol relabelings S n S_n S n . Hence the configuration space decomposes into level sets L t = { x : H p e n ( x ) : = ⟨ x ∣ H p e n ∣ x ⟩ = t } L_t = \{x : H_{\mathrm{pen}}(x) := \langle x \mid H_{\mathrm{pen}} \mid x\rangle= t\} L t = { x : H pen ( x ) := ⟨ x ∣ H pen ∣ x ⟩ = t } that are preserved setwise.
(c) In addition, the initial state is the + 1 +1 + 1 eigenstate of the block-local normalized XY mixer Hamiltonian,
H ~ M ( b ) = 1 n − 1 ∑ 0 ≤ j < k ≤ n − 1 ( X j ( b ) X k ( b ) + Y j ( b ) Y k ( b ) ) , \widetilde{H}^{(b)}_M = \frac{1}{n-1}\sum_{0\le j<k\le n-1}\left(X_j^{(b)}X_k^{(b)}+Y_j^{(b)}Y_k^{(b)}\right), H M ( b ) = n − 1 1 0 ≤ j < k ≤ n − 1 ∑ ( X j ( b ) X k ( b ) + Y j ( b ) Y k ( b ) ) , with ∥ H ~ M ( b ) ∥ = O ( 1 ) \lVert\widetilde{H}^{(b)}_M\rVert= O(1) ∥ H M ( b ) ∥ = O ( 1 ) on each block. The initial state is the uniform one-hot product
∣ s 0 ⟩ = ∣ s b ⟩ ⊗ m , ∣ s b ⟩ = 1 n ∑ k = 0 n − 1 ∣ e k ⟩ (a W n state per block). \lvert s_0\rangle= \lvert s_b\rangle^{\otimes m}, \qquad\lvert s_b\rangle= \frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\lvert e_k\rangle\quad\text{(a $W_n$ state per block).} ∣ s 0 ⟩ = ∣ s b ⟩ ⊗ m , ∣ s b ⟩ = n 1 k = 0 ∑ n − 1 ∣ e k ⟩ (a W n state per block).
Although the kernel above fixes one-hot blocks (1 excitation per block), many applications naturally use k k k -hot blocks (fixed Hamming weight of k k k per block). In that case, one replaces H 1 \mathcal{H}_1 H 1 by H k = span { ∣ x ⟩ ∈ { 0 , 1 } n : ∥ x ∥ 1 = k } \mathcal{H}_k = \operatorname{span}\{\lvert x\rangle\in\{0,1\}^n : \lVert x\rVert_1 = k\} H k = span {∣ x ⟩ ∈ { 0 , 1 } n : ∥ x ∥ 1 = k } , and chooses a suitable number-conserving block-local mixer (e.g. modified XY Hamiltonian, which preserves excitation number) normalized to constant operator norm on H k \mathcal{H}_k H k . The corresponding initial state becomes a tensor product of Dicke states encoders [39 ] ,
∣ s b ( k ) ⟩ = ∣ D k ( n ) ⟩ = ( n k ) − 1 2 ∑ x ∈ { 0 , 1 } n ∥ x ∥ 1 = k ∣ x ⟩ , ∣ s 0 ⟩ = ( ∣ D k ( n ) ⟩ ) ⊗ m . \left|s_b^{(k)}\right\rangle=\left|D_k^{(n)}\right\rangle=\binom{n}{k}^{-\frac{1}{2}}\sum_{\substack{x\in\{0,1\}^{n}\\ \lVert x\rVert_1=k}}|x\rangle,\qquad|s_0\rangle=\left(\left|D_k^{(n)}\right\rangle\right)^{\otimes m}. s b ( k ) ⟩ = D k ( n ) ⟩ = ( k n ) − 2 1 x ∈ { 0 , 1 } n ∥ x ∥ 1 = k ∑ ∣ x ⟩ , ∣ s 0 ⟩ = ( D k ( n ) ⟩ ) ⊗ m .
This further enlarges the class of constrained combinatorial optimization problems that can fit into the kernel proposed above. Some identified problem classes include: Travelling Salesman (TSP/ATSP) [40 , 41 ] , Quadratic Assignment Problem (QAP) [42 , 43 ] , Vehicle Routing with Capacities (CVRP) [3 ] , Generalized Assignment / Multiple-Knapsack [44 , 45 ] , k k k D Matching (NP-complete for k ≥ 3 k \ge3 k ≥ 3 ) [46 , 47 ] , the shared transportation problems [27 ] , and Job–Shop / Flow–Shop Scheduling [48 , 49 ] . Some base cases (e.g., linear assignment) are polynomial-time solvable via the Hungarian algorithm [26 , 50 ] ; nevertheless, they fit the kernel structurally. Our interest is in the NP-hard variants (e.g., TSP/QAP/CVRP, etc.) for which the same one-hot encodings and symmetries apply.
Definition 2 (Feasible basis vectors). Let H O H = H 1 ⊗ m \mathcal{H}_{\mathrm{OH}}=\mathcal{H}_1^{\otimes m} H OH = H 1 ⊗ m denote the encoded one-hot product space from Definition 1, and let
H C = H p e n + H o b j H_{\mathrm{C}}=H_{\mathrm{pen}}+H_{\mathrm{obj}} H C = H pen + H obj be the problem Hamiltonian with H p e n H_{\mathrm{pen}} H pen satisfying the kernel symmetries. A computational basis vector ∣ x ⟩ |x\rangle ∣ x ⟩ with block decomposition x = ( j 0 , … , j m − 1 ) ∈ [ n ] m x=(j_0,\ldots,j_{m-1})\in[n]^m x = ( j 0 , … , j m − 1 ) ∈ [ n ] m is called feasible if and only if
H p e n ( x ) : = ⟨ x ∣ H p e n ∣ x ⟩ = 0 , H_{\mathrm{pen}}(x):=\langle x|H_{\mathrm{pen}}|x\rangle=0, H pen ( x ) := ⟨ x ∣ H pen ∣ x ⟩ = 0 , i.e. ∣ x ⟩ |x\rangle ∣ x ⟩ lies in the zero-penalty level set
L 0 ( H p e n ) : = { ∣ x ⟩ ∈ H O H : H p e n ( x ) = 0 } . L_0(H_{\mathrm{pen}}):=\{|x\rangle\in\mathcal{H}_{\mathrm{OH}}:H_{\mathrm{pen}}(x)=0\}. L 0 ( H pen ) := { ∣ x ⟩ ∈ H OH : H pen ( x ) = 0 } .
The Initial State Preparation Protocol
Consider some n × m n\times m n × m -qubit system where n n n can be considered of a fixed size repeated m m m times. Suppose each block has n n n qubits, and consider a single excitation subspace spanned by the equal superposition ∣ s ⟩ = 1 n ∑ k = 0 n − 1 ∣ e k ⟩ |s\rangle=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}|e_k\rangle ∣ s ⟩ = n 1 ∑ k = 0 n − 1 ∣ e k ⟩ . Over the m m m blocks, the final state is:
∣ s 0 ⟩ = ⨂ b = 0 m − 1 ( 1 n ∑ k = 0 n − 1 ∣ e k ⟩ ) , (1) |s_0\rangle=\bigotimes_{b=0}^{m-1}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}|e_k\rangle\right), \tag*{(1)} ∣ s 0 ⟩ = b = 0 ⨂ m − 1 ( n 1 k = 0 ∑ n − 1 ∣ e k ⟩ ) , (1)
realising block-wise tensor product of uniform W-states [51 , 39 ] . Algorithm 1, a simple cascade-style algorithm can prepare the initial state described above in Eq (1) ; obtaining a single block of n n n qubits in a W-state. Then Algorithm 2 (**OneHotMultiBlockPrepare(m m m )}) uses the single-block procedure on each of the m m m blocks to create a W-state per block. The total Hamming weight per bitstring is fixed and the Hamming Geometry is constrained by the location of single excitation contributed by each block. This circuit construction scales optimally in gate depth on a linear array.
Theorem 4 (Gate–depth optimality on a line). There exists an ancilla-free circuit that prepares ∣ W n ⟩ \lvert W_n\rangle ∣ W n ⟩ on a linear array using n − 1 n-1 n − 1 two-qubit excitation-preserving rotations
U M ( k , k + 1 ) ( ϕ ) : = exp [ − i ϕ 2 ( X k X k + 1 + Y k Y k + 1 ) ] , U_{M}^{(k,k+1)}(\phi) := \exp\left[-i\frac{\phi}{2}\left(X_kX_{k+1}+Y_kY_{k+1}\right)\right], U M ( k , k + 1 ) ( ϕ ) := exp [ − i 2 ϕ ( X k X k + 1 + Y k Y k + 1 ) ] , on each adjacent pair ( k , k + 1 ) (k,k+1) ( k , k + 1 ) , with suitable angles { ϕ k } k = 0 n − 1 \{\phi_k\}_{k=0}^{n-1} { ϕ k } k = 0 n − 1 . Moreover, any circuit over single-qubit gates and two-qubit gates on a linear array that prepares ∣ W n ⟩ \lvert W_n\rangle ∣ W n ⟩ must use at least n − 1 n-1 n − 1 two-qubit gates.
Proof. Label qubits 0 , 1 , 2 , … , n − 1 0,1,2,\ldots,n-1 0 , 1 , 2 , … , n − 1 on a line and, for each k = 0 , … , n − 1 k=0,\ldots,n-1 k = 0 , … , n − 1 , consider the bipartition { 0 , … , k } ∣ { k + 1 , … , n − 1 } \{0,\ldots,k\}\mid\{k+1,\ldots,n-1\} { 0 , … , k } ∣ { k + 1 , … , n − 1 } . For the uniform W W W -state ∣ W n ⟩ = 1 n ∑ k = 0 n − 1 ∣ 0 ⋯ 1 k ⋯ 0 ⟩ \lvert W_n\rangle=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\lvert0\cdots1_k\cdots0\rangle ∣ W n ⟩ = n 1 ∑ k = 0 n − 1 ∣ 0 ⋯ 1 k ⋯ 0 ⟩ , the Schmidt rank across every such single-edge cut is SR k ( ∣ W n ⟩ ) = 2 \operatorname{SR}_k(\lvert W_n\rangle)=2 SR k (∣ W n ⟩) = 2 . The product state ∣ 0 ⟩ ⊗ n \lvert0\rangle^{\otimes n} ∣ 0 ⟩ ⊗ n has rank 1 across every cut. A two-qubit gate that does not cross a given cut cannot increase that cut’s rank, while a two-qubit gate that does cross it can increase the rank by at most a factor of 2. Thus each of the n − 1 n-1 n − 1 adjacency cuts must be crossed at least once by a two-qubit gate, so any preparation requires ≥ n − 1 \ge n-1 ≥ n − 1 two-qubit gates. Alg. 1 gives a construction that achieves the bound.
Remark 5 (Hardware-friendly alternatives). On platforms with native iSWAPα ^\alpha α or fSim( θ , ϕ ) (\theta,\phi) ( θ , ϕ ) , U M ( k , k + 1 ) ( ϕ ) U_{M}^{(k,k+1)}(\phi) U M ( k , k + 1 ) ( ϕ ) is implementable in one entangling gate (up to single-qubit Z Z Z phases). If X X + Y Y XX+YY X X + Y Y is not native, one can realize the same two-level rotation on the preparation path with the single 2Q primitive
U ~ ( θ ) : = CX k + 1 → k ⋅ CRY k → k + 1 ( θ ) \widetilde{U}(\theta):=\operatorname{CX}_{k+1\to k}\cdot\operatorname{CRY}_{k\to k+1}(\theta) U ( θ ) := CX k + 1 → k ⋅ CRY k → k + 1 ( θ ) with θ = 2 ϕ \theta=2\phi θ = 2 ϕ , which has the block action ∣ 10 ⟩ ↦ cos ( θ 2 ) ∣ 10 ⟩ + sin ( θ 2 ) ∣ 01 ⟩ \lvert10\rangle\mapsto\cos\left(\frac{\theta}{2}\right)\lvert10\rangle+\sin\left(\frac{\theta}{2}\right)\lvert01\rangle ∣ 10 ⟩ ↦ cos ( 2 θ ) ∣ 10 ⟩ + sin ( 2 θ ) ∣ 01 ⟩ on span { ∣ 10 ⟩ , ∣ 01 ⟩ } \operatorname{span}\{\lvert10\rangle,\lvert01\rangle\} span {∣ 10 ⟩ , ∣ 01 ⟩} .
Algorithm 1 OneHotBlockPrepare( n ) (n) ( n ) — exact single-excitation W n W_n W n
Require: number of qubits n ≥ 2 n\ge2 n ≥ 2 labelled 0 , … , n − 1 0,\ldots,n-1 0 , … , n − 1
For adjacent qubits ( k , k + 1 ) (k,k+1) ( k , k + 1 ) , let
U ( k , k + 1 ) ( θ ) : = exp [ − i θ 2 ( X k X k + 1 + Y k Y k + 1 ) ] U^{(k,k+1)}(\theta):=\exp\left[-i\frac{\theta}{2}\left(X_kX_{k+1}+Y_kY_{k+1}\right)\right] U ( k , k + 1 ) ( θ ) := exp [ − i 2 θ ( X k X k + 1 + Y k Y k + 1 ) ] ▹ \triangleright ▹ acts as a real Givens rotation on span { ∣ 10 ⟩ , ∣ 01 ⟩ } \operatorname{span}\{\lvert10\rangle,\lvert01\rangle\} span {∣ 10 ⟩ , ∣ 01 ⟩} (Hardware alternative: U ( k , k + 1 ) ( θ ) = CX k + 1 → k ⋅ CRY k → k + 1 ( θ ) U^{(k,k+1)}(\theta)=\operatorname{CX}_{k+1\to k}\cdot\operatorname{CRY}_{k\to k+1}(\theta) U ( k , k + 1 ) ( θ ) = CX k + 1 → k ⋅ CRY k → k + 1 ( θ ) )
Apply X X X on qubit 0 ▹ ∣ 100 … 0 ⟩ \triangleright\lvert100\ldots0\rangle ▹ ∣ 100 … 0 ⟩
for k ← 0 k\leftarrow0 k ← 0 to n − 2 n-2 n − 2 do
θ k ← 2 arccos ( 1 n − k ) \theta_k\leftarrow2\arccos\left(\frac{1}{\sqrt{n-k}}\right) θ k ← 2 arccos ( n − k 1 )
Apply U ( k , k + 1 ) ( θ k ) U^{(k,k+1)}(\theta_k) U ( k , k + 1 ) ( θ k ) ▹ \triangleright ▹ fixes amplitude on site k k k to 1 / n 1/\sqrt{n} 1/ n
end for
Ensure: ∣ W n ⟩ = 1 n ∑ k = 0 n − 1 ∣ 0 … 1 k … 0 ⟩ \lvert W_n\rangle=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\lvert0\ldots1_k\ldots0\rangle ∣ W n ⟩ = n 1 ∑ k = 0 n − 1 ∣ 0 … 1 k … 0 ⟩
Algorithm 2 OneHotMultiBlockPrepare($m$) — tensor product of $m$ $W$-blocks
Require: block size $n$, number of blocks $m$
1: for $b \leftarrow 0$ to $m - 1$ do
2: Apply OneHotBlockPrepare($n$) on qubits $bn$, $bn+1$, $\ldots$, $(b+1)n - 1$
3: end for
Ensure:
$$
(\lvert W_n\rangle)^{\otimes m} = \frac{1}{\sqrt{n^m}} \sum_{\substack{k_0,\ldots,k_{m-1}\\ \in\{0,\ldots,n-1\}}} \bigotimes_{b=0}^{m-1} \lvert 0\ldots 1_{k_b}\ldots 0\rangle
$$
It follows from well known results in quantum circuit simulation that the initial state prepared by Algorithm 2 is non-stabilizer for n ≥ 3 n \ge3 n ≥ 3 [53 ] because each block contains a W n W_n W n -state. We cite this result in the following proposition.
Proposition 6 (W n W_n W n is non-Clifford [53 ] ). For n ≥ 3 n \ge3 n ≥ 3 the n n n -qubit W W W state ∣ W n ⟩ = 1 n ∑ k = 0 n − 1 ∣ e k ⟩ \lvert W_n\rangle= \frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\lvert e_k\rangle ∣ W n ⟩ = n 1 ∑ k = 0 n − 1 ∣ e k ⟩ is not a stabilizer state. In particular, it cannot be prepared from ∣ 0 ⟩ ⊗ n \lvert0\rangle^{\otimes n} ∣ 0 ⟩ ⊗ n using Clifford operations alone. (The edge case W 2 = ( ∣ 01 ⟩ + ∣ 10 ⟩ ) / 2 W_2 = (\lvert01\rangle+ \lvert10\rangle)/\sqrt{2} W 2 = (∣ 01 ⟩ + ∣ 10 ⟩) / 2 is stabilizer.) Outside the stabilizer regime, strong simulation typically relies on non-Clifford techniques which are not known to run in polynomial time in general [53 ] .
It is thus reasonable to expect that our encoder already places the ansatz beyond the efficiently simulable stabilizer regime, strengthening the potential for quantum–classical separation discussed in § 3.3 and 4.3. Figure 1 shows the basis vectors forming a product of one-hot states in the reduced Hilbert space with bitstrings representing valid permutations marked in green. Figure 2 is a single layer CE-QAOA circuit for a 12 qubit problem with 3 blocks[31 ] .2
Figure 1. Histogram produced in Qiskit[52 ] for a TSP problem on 3 locations. Each of the 3 3 = 27 3^3 = 27 3 3 = 27 block–one-hot bit-strings carries probability 1 / 27 1/27 1/27 verifying that the state–preparation algorithm populates all basis states with equal amplitude while leaving probability mass strictly inside the one-hot subspace. The six strings whose block indices form a permutation are coloured green.
Figure 2. Depth-p = 3 p=3 p = 3 CE-QAOA for m = 3 m=3 m = 3 blocks of n = 4 n=4 n = 4 qubits. Each layer applies a global cost U C ( γ ℓ ) U_C(\gamma_\ell) U C ( γ ℓ ) over all m n mn mn wires, followed by parallel block-local XY mixers U M ( j ) ( β ℓ ) U_M^{(j)}(\beta_\ell) U M ( j ) ( β ℓ ) .
The XY Mixer Operator
Recall that the task in QAOA+ is to construct, for the initial state, a suitable mixer Hamiltonian such that the initial state is its + 1 +1 + 1 eigenstate[18 , 17 ] . Thus, we require an XY mixer Hamiltonian that preserves the one–hot subspace. For each n n n -qubit block b b b we define (up to constant prefactor)
H M ( b ) = ∑ 0 ≤ i < j ≤ n − 1 ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) (2) H_M^{(b)}=\sum_{0\le i<j\le n-1}\left(X_i^{(b)}X_j^{(b)}+Y_i^{(b)}Y_j^{(b)}\right) \tag*{(2)} H M ( b ) = 0 ≤ i < j ≤ n − 1 ∑ ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) (2)
where X i ( b ) X_i^{(b)} X i ( b ) and Y i ( b ) Y_i^{(b)} Y i ( b ) denote the Pauli X X X and Y Y Y operators acting on the i i i th qubit in block b b b . The overall mixer unitary is given by
U M ( β ) = U M ( 0 ) ( β ) ⊗ ⋯ ⊗ U M ( m − 1 ) ( β ) . (3) U_M(\beta)=U_M^{(0)}(\beta)\otimes\cdots\otimes U_M^{(m-1)}(\beta). \tag*{(3)} U M ( β ) = U M ( 0 ) ( β ) ⊗ ⋯ ⊗ U M ( m − 1 ) ( β ) . (3)
Where U M ( b ) ( β ) = e − i β H M ( b ) U_M^{(b)}(\beta)=e^{-i\beta H_M^{(b)}} U M ( b ) ( β ) = e − i β H M ( b ) for each block. The construction is outlined in Algorithm 3. See Figure 2 for the blockwise construction depicted in a full circuit.
In terms of the dynamics, the XY Mixer continuously mixes the valid one-hot basis states among themselves thanks to its adjacency and ergodicity properties on the H 1 \mathcal{H}_1 H 1 subspace. To expose these properties, it is helpful to rewrite the mixer Hamiltonian in a form that is manifestly 2-local and preserves the excitation number. The mixer Hamiltonian is:
H M ( b ) : = ∑ 0 ≤ i < j ≤ n − 1 ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) = ∑ i < j ( σ b i + σ b j − + σ b i − σ b j + ) (4) H_M^{(b)}:=\sum_{0\le i<j\le n-1}\left(X_i^{(b)}X_j^{(b)}+Y_i^{(b)}Y_j^{(b)}\right)=\sum_{i<j}\left(\sigma_{bi}^{+}\sigma_{bj}^{-}+\sigma_{bi}^{-}\sigma_{bj}^{+}\right) \tag*{(4)} H M ( b ) := 0 ≤ i < j ≤ n − 1 ∑ ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) = i < j ∑ ( σ bi + σ bj − + σ bi − σ bj + ) (4)
Restricting attention to the one-excitation subspace H 1 = span { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩ } \mathcal{H}_1=\operatorname{span}\{\lvert e_0\rangle,\ldots,\lvert e_{n-1}\rangle\} H 1 = span {∣ e 0 ⟩ , … , ∣ e n − 1 ⟩} , and normalising by n n n gives H ~ M ( b ) : = H M ( b ) / n \widetilde{H}_M^{(b)}:=H_M^{(b)}/n H M ( b ) := H M ( b ) / n with constant spectral gap . (cf. App. § 6 .§ 3 ).
Table 3.
Proposition 7 (Spectral gap of one-block XY mixer). On H 1 \mathcal{H}_1 H 1 the operator H M ( b ) H_M^{(b)} H M ( b ) acts as the adjacency matrix A ( K n ) A(K_n) A ( K n ) of the complete graph on n n n vertices and has spectrum
spec ( H M ( b ) ∣ H 1 ) = { n − 1 , − 1 , … , − 1 } . \operatorname{spec}\left(H_M^{(b)}\big|_{\mathcal{H}_1}\right)=\{n-1,-1,\ldots,-1\}. spec ( H M ( b ) H 1 ) = { n − 1 , − 1 , … , − 1 } . Hence the spectral gap is Δ ( H M ( b ) ) = n \Delta(H_M^{(b)})=n Δ ( H M ( b ) ) = n . H ~ M ( b ) = H M ( b ) / n \widetilde{H}_M^{(b)}=H_M^{(b)}/n H M ( b ) = H M ( b ) / n has constant gap Δ ( H ~ M ( b ) ) = 1 \Delta(\widetilde{H}_M^{(b)})=1 Δ ( H M ( b ) ) = 1 .
Proof. Acting on a basis state with the excitation at site i i i with Eq. (4) (See App. § 6 .§ 3 ),
( X i X j + Y i Y j ) ∣ e i ⟩ = σ i − σ j + ∣ e i ⟩ = ∣ e j ⟩ , (X_iX_j+Y_iY_j)\lvert e_i\rangle=\sigma_i^{-}\sigma_j^{+}\lvert e_i\rangle=\lvert e_j\rangle, ( X i X j + Y i Y j ) ∣ e i ⟩ = σ i − σ j + ∣ e i ⟩ = ∣ e j ⟩ ,
while the same operator annihilates ∣ e k ⟩ \lvert e_k\rangle ∣ e k ⟩ for k ∉ { i , j } k\notin\{i,j\} k ∈ / { i , j } . Summing over all unordered pairs ( i , j ) (i,j) ( i , j ) therefore maps ∣ e i ⟩ ↦ ∑ j ≠ i ∣ e j ⟩ \lvert e_i\rangle\mapsto\sum_{j\ne i}\lvert e_j\rangle ∣ e i ⟩ ↦ ∑ j = i ∣ e j ⟩ , which is exactly the action of the adjacency matrix A ( K n ) A(K_n) A ( K n ) on the standard vertex basis. The spectrum of A ( K n ) A(K_n) A ( K n ) is well known from spectral graph theory [54 ] . Largest eigenvalue λ max = n − 1 \lambda_{\max}=n-1 λ m a x = n − 1 (eigenvector 1 n ∑ k ∣ e k ⟩ \frac{1}{\sqrt{n}}\sum_k\lvert e_k\rangle n 1 ∑ k ∣ e k ⟩ ) and the remaining n − 1 n-1 n − 1 eigenvalues equal − 1 -1 − 1 . Hence Δ ( H M ( b ) ) = ( n − 1 ) − ( − 1 ) = n \Delta(H_M^{(b)})=(n-1)-(-1)=n Δ ( H M ( b ) ) = ( n − 1 ) − ( − 1 ) = n . Dividing by n n n rescales both extremal eigenvalues by the same factor, so Δ ( H ~ M ( b ) ) = 1 \Delta(\widetilde{H}^{(b)}_M)=1 Δ ( H M ( b ) ) = 1 . The claimed constant spectral gap and K n K_n K n denotes its complete adjacency graph.
Proposition 8 (Ergodicity of the angle-averaged XY mixer on H 1 \mathcal{H}_1 H 1 ). Consider a single n n n -qubit one-hot block with one-excitation sector H 1 = span { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩ } \mathcal{H}_1=\operatorname{span}\{\lvert e_0\rangle,\ldots,\lvert e_{n-1}\rangle\} H 1 = span {∣ e 0 ⟩ , … , ∣ e n − 1 ⟩} . Let H M ( b ) ∣ H 1 = A ( K n ) H^{(b)}_M\big|_{\mathcal{H}_1}=A(K_n) H M ( b ) H 1 = A ( K n ) be the restriction of the all-to-all unnormalised X Y XY X Y Hamiltonian to H 1 \mathcal{H}_1 H 1 (equivalently, the adjacency matrix of the complete graph on n n n vertices up to an overall scalar). For β ∈ R \beta\in\mathbb{R} β ∈ R define U ( β ) : = e − i β H M ( b ) U(\beta):=e^{-i\beta H^{(b)}_M} U ( β ) := e − i β H M ( b ) and the transition matrix
P i j : = ∫ 0 2 π d β 2 π ∣ ⟨ e j ∣ U ( β ) ∣ e i ⟩ ∣ 2 , 0 ≤ i , j ≤ n − 1. P_{ij}:=\int_{0}^{2\pi}\frac{\mathrm{d}\beta}{2\pi}\left|\langle e_j|U(\beta)|e_i\rangle\right|^2,\qquad0\leq i,j\leq n-1. P ij := ∫ 0 2 π 2 π d β ∣ ⟨ e j ∣ U ( β ) ∣ e i ⟩ ∣ 2 , 0 ≤ i , j ≤ n − 1. Then:
P P P is primitive (all entries are strictly positive), hence the associated Markov chain is ergodic (irreducible and aperiodic).
P P P is doubly stochastic, and its unique stationary distribution is the uniform distribution π ⋆ = ( 1 / n , … , 1 / n ) \pi^\star=(1/n,\ldots,1/n) π ⋆ = ( 1/ n , … , 1/ n ) .
Explicitly,
P i i = 1 − 2 n + 2 n 2 , P i j = 2 n 2 ( j ≠ i ) , P_{ii}=1-\frac{2}{n}+\frac{2}{n^2},\qquad P_{ij}=\frac{2}{n^2}\quad(j\ne i), P ii = 1 − n 2 + n 2 2 , P ij = n 2 2 ( j = i ) , so that P t → 1 π ⋆ T P^t\to\mathbf{1}\,\pi^{\star\mathsf{T}} P t → 1 π ⋆ T as t → ∞ t\to\infty t → ∞ .
These conclusions are invariant under any nonzero rescaling H M ( b ) ↦ c H M ( b ) H^{(b)}_M\mapsto cH^{(b)}_M H M ( b ) ↦ c H M ( b ) , c ∈ R ∖ { 0 } c\in\mathbb{R}\setminus\{0\} c ∈ R ∖ { 0 } .
Proof. On H 1 \mathcal{H}_1 H 1 , H M ( b ) H^{(b)}_M H M ( b ) has spectral decomposition H M ( b ) = ( n − 1 ) Π s + ( − 1 ) Π ⊥ H^{(b)}_M=(n-1)\Pi_s+(-1)\Pi_\perp H M ( b ) = ( n − 1 ) Π s + ( − 1 ) Π ⊥ , where Π s = ∣ s ⟩ ⟨ s ∣ \Pi_s=\lvert s\rangle\langle s\rvert Π s = ∣ s ⟩ ⟨ s ∣ with ∣ s ⟩ = 1 n ∑ k = 0 n − 1 ∣ e k ⟩ \lvert s\rangle=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\lvert e_k\rangle ∣ s ⟩ = n 1 ∑ k = 0 n − 1 ∣ e k ⟩ and Π ⊥ = I − Π s \Pi_\perp=I-\Pi_s Π ⊥ = I − Π s . Hence
U ( β ) = e − i β ( n − 1 ) Π s + e + i β Π ⊥ . U(\beta)=e^{-i\beta(n-1)}\Pi_s+e^{+i\beta}\Pi_\perp. U ( β ) = e − i β ( n − 1 ) Π s + e + i β Π ⊥ . For basis states, ⟨ e j ∣ U ( β ) ∣ e i ⟩ = e − i β ( n − 1 ) 1 n + e + i β ( δ i j − 1 n ) \langle e_j|U(\beta)|e_i\rangle=e^{-i\beta(n-1)}\frac{1}{n}+e^{+i\beta}\left(\delta_{ij}-\frac{1}{n}\right) ⟨ e j ∣ U ( β ) ∣ e i ⟩ = e − i β ( n − 1 ) n 1 + e + i β ( δ ij − n 1 ) . Averaging ∣ ⋅ ∣ 2 \lvert\cdot\rvert^2 ∣ ⋅ ∣ 2 over β ∈ [ 0 , 2 π ) \beta\in[0,2\pi) β ∈ [ 0 , 2 π ) removes cross terms (orthogonal Fourier modes), giving
P i j = 1 n 2 + ( δ i j − 1 n ) 2 = { 1 − 2 n + 2 n 2 , j = i , 2 n 2 , j ≠ i . P_{ij}=\frac{1}{n^2}+\left(\delta_{ij}-\frac{1}{n}\right)^2=
\begin{cases}
1-\frac{2}{n}+\frac{2}{n^2}, & j=i,\\
\frac{2}{n^2}, & j\ne i.
\end{cases} P ij = n 2 1 + ( δ ij − n 1 ) 2 = { 1 − n 2 + n 2 2 , n 2 2 , j = i , j = i . All entries are strictly positive, so P P P is primitive (hence ergodic). Row and column sums are 1 by symmetry, so P P P is doubly stochastic and the uniform distribution is the unique stationary distribution. Convergence P t → 1 π ⋆ T P^t\to\mathbf{1}\,\pi^{\star\mathsf{T}} P t → 1 π ⋆ T follows from primitivity. If H M ( b ) H^{(b)}_M H M ( b ) is rescaled by a c > 0 c>0 c > 0 , the averaged cross terms still vanish and the same P P P formula holds. In particular it holds for H ~ M ( b ) \widetilde{H}^{(b)}_M H M ( b ) .
Local unitary designs make extensive use of qudit language. Since t-designs are central to our methods, following Ref. [14 ] , we formulate the qudit ↔ \leftrightarrow ↔ qubit isometry below.
Definition 9 (Encoding isometry (q u b i t ↔ q u d i t qubit\leftrightarrow qudit q u bi t ↔ q u d i t )). Let C n \mathbb{C}^n C n be the abstract qudit space with basis { ∣ j ⟩ } j = 0 n − 1 \{\lvert j\rangle\}_{j=0}^{n-1} {∣ j ⟩ } j = 0 n − 1 . Define the isometry
V : C n ⟶ ( C 2 ) ⊗ n , V ∣ j ⟩ = ∣ e j ⟩ . V:\mathbb{C}^n\longrightarrow(\mathbb{C}^2)^{\otimes n},\qquad V\lvert j\rangle=\lvert e_j\rangle. V : C n ⟶ ( C 2 ) ⊗ n , V ∣ j ⟩ = ∣ e j ⟩ . Then V † V = I n V^\dagger V=I_n V † V = I n and V V † VV^\dagger V V † is the projector onto H 1 \mathcal{H}_1 H 1 .
Proposition 10 (Invariance and quditization of the block–XY mixer). Let
H M ( b ) = ∑ 0 ≤ i < j ≤ n − 1 ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) = ∑ i ≠ j σ b i ( b ) σ b j ( b ) H^{(b)}_M=\sum_{0\leq i<j\leq n-1}\left(X_i^{(b)}X_j^{(b)}+Y_i^{(b)}Y_j^{(b)}\right)=\sum_{i\ne j}\sigma_{b_i}^{(b)}\sigma_{b_j}^{(b)} H M ( b ) = 0 ≤ i < j ≤ n − 1 ∑ ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) = i = j ∑ σ b i ( b ) σ b j ( b ) on the n n n qubits of a block. Then:
H 1 \mathcal{H}_1 H 1 is invariant under H M ( b ) H_{\mathrm{M}}^{(\mathrm{b})} H M ( b ) and U ( b ) ( β ) : = e − i β H M ( b ) U^{(\mathrm{b})}(\beta) := e^{-i\beta H_{\mathrm{M}}^{(\mathrm{b})}} U ( b ) ( β ) := e − i β H M ( b ) .
In the encoded qudit picture,
V † H M ( b ) V = ∑ i ≠ j ∣ i ⟩ ⟨ j ∣ = A ( K n ) , V^\dagger H_{\mathrm{M}}^{(\mathrm{b})} V = \sum_{i\ne j} |i\rangle\langle j| = A(K_n), V † H M ( b ) V = i = j ∑ ∣ i ⟩ ⟨ j ∣ = A ( K n ) ,
the adjacency matrix of the complete graph K n K_n K n . Consequently, U ( b ) ( β ) = V e − i β A ( K n ) V † U^{(\mathrm{b})}(\beta) = V e^{-i\beta A(K_n)} V^\dagger U ( b ) ( β ) = V e − i β A ( K n ) V † on H 1 \mathcal{H}_1 H 1 .
Proof. For any single-excitation basis vector ∣ e j ⟩ |e_j\rangle ∣ e j ⟩ , σ i + σ j − ∣ e j ⟩ = ∣ e i ⟩ \sigma_i^+\sigma_j^-|e_j\rangle= |e_i\rangle σ i + σ j − ∣ e j ⟩ = ∣ e i ⟩ and σ i + σ j − ∣ e k ⟩ = 0 \sigma_i^+\sigma_j^-|e_k\rangle= 0 σ i + σ j − ∣ e k ⟩ = 0 if k ∉ { i , j } k \notin\{i,j\} k ∈ / { i , j } . Thus H M ( b ) H_{\mathrm{M}}^{(\mathrm{b})} H M ( b ) maps ∣ e j ⟩ |e_j\rangle ∣ e j ⟩ to a superposition of { ∣ e i ⟩ } \{|e_i\rangle\} { ∣ e i ⟩} , so H 1 \mathcal{H}_1 H 1 and U ( b ) ( β ) U^{(\mathrm{b})}(\beta) U ( b ) ( β ) are invariant. Moreover, V † σ i + σ j − V = ∣ i ⟩ ⟨ j ∣ V^\dagger\sigma_i^+\sigma_j^-V = |i\rangle\langle j| V † σ i + σ j − V = ∣ i ⟩ ⟨ j ∣ , ( i ≠ j ) (i\ne j) ( i = j ) , hence the claimed identification with A ( K n ) A(K_n) A ( K n ) .
Constraint-Enhanced QAOA Protocol
The next key ingredient is the cost Hamiltonian H C H_C H C that represents the optimization problem and constraints. This is usually the Ising Hamiltonian corresponding to the problem and thus diagonal in the computational basis. The full circuit with p p p layers alternates between the cost and mixer unitaries a set of parameters (respectively) γ ⃗ = ( γ 1 , … , γ p ) \vec{\gamma} = (\gamma_1,\ldots,\gamma_p) γ = ( γ 1 , … , γ p ) and β ⃗ = ( β 1 , … , β p ) \vec{\beta} = (\beta_1,\ldots,\beta_p) β = ( β 1 , … , β p ) . Algebraically, the circuit is represented by the following:
∣ ψ p ( γ ⃗ , β ⃗ ) ⟩ = ( ∏ l = 1 p e − i β l H M e − i γ l H C ) ∣ s 0 ⟩ . (5) |\psi_p(\vec{\gamma},\vec{\beta})\rangle= \left(\prod_{l=1}^{p} e^{-i\beta_l H_M}e^{-i\gamma_l H_C}\right)|s_0\rangle. \tag*{(5)} ∣ ψ p ( γ , β )⟩ = ( l = 1 ∏ p e − i β l H M e − i γ l H C ) ∣ s 0 ⟩ . (5)
The Alg. 2 prepares ∣ s 0 ⟩ |s_0\rangle ∣ s 0 ⟩ and initializes the quantum dynamics in the constrained fixed-Hamming-weight space H O H = ( H 1 ) ⊗ m \mathcal{H}_{\mathrm{OH}} = (\mathcal{H}_1)^{\otimes m} H OH = ( H 1 ) ⊗ m . Because the cost Hamiltonian H C H_C H C is diagonal in the computational basis, we have U C ( γ ) ∣ x ⟩ ∈ H O H U_C(\gamma)|x\rangle\in\mathcal{H}_{\mathrm{OH}} U C ( γ ) ∣ x ⟩ ∈ H OH for all product basis states ∣ x ⟩ ∈ H O H |x\rangle\in\mathcal{H}_{\mathrm{OH}} ∣ x ⟩ ∈ H OH and it never mixes amplitudes or leaks outside the one-hot subspace. The overall depth increase from our construction, if any, is minimal. The following holds.
Corollary 11 (Block size limits circuit depth). Let the block-structured QAOA ansatz consist of m m m disjoint blocks, each acting on n n n qubits. Then, under the assumption of parallel execution across blocks, the circuit depth of the full initial state preparation unitary is D p r e p = D b l o c k − p r e p D_{\mathrm{prep}} = D_{\mathrm{block-prep}} D prep = D block − prep , and the depth of the full mixer unitary is D m i x = D b l o c k − m i x D_{\mathrm{mix}} = D_{\mathrm{block-mix}} D mix = D block − mix . Hence, the overall depth overhead is independent of the number of blocks m m m .
Resource savings from co-design. Suprisingly, the co-designed restriction to the one-hot manifold can reduce quantum resources relative to the standard QAOA formulation[7 ] . For permutation-constrained problems (e.g., TSP), feasibility imposes a double one-hot structure (row and column constraints) on the permutation matrix. In CE-QAOA, the chosen initial state and block-XY mixer preserve the row-wise one-hot condition by construction, so those constraint terms are redundant and can be dropped from the diagonal phase operator; only the complementary (e.g., column-wise) constraints need to be enforced. This eliminates an entire family of penalty interactions and yields an O ( n ) O(n) O ( n ) reduction in the depth (and two-qubit gate count) of the phase-separation unitary compared to standard QAOA implementations. Corollary 11 already shows that the additional overhead from the proposed state preparation and mixing does not scale with the number of blocks m m m under parallel execution, so the net effect can be a strict depth reduction. For example, the O ( n ) O(n) O ( n ) savings from removing redundant penalties can dominate the O ( n ) O(n) O ( n ) preparation cost on architectures with native (or efficiently compiled) excitation-preserving rotations leading to an overall circuit depth smaller than that of a generic QAOA.
Crucially, these resource savings do not come from limiting the reachable set of feasible states. On the contrary, in the next proposition we show that the same block-local, constraint-preserving operations are controllable (and approximately universal) within each block .
Proposition 12 (Controllability and approximate universality on H 1 \mathcal{H}_1 H 1 ). Fix a single n n n -qubit one-hot block and the operator set
G : = { H i j ( b ) = X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) : 0 ≤ i < j ≤ n − 1 , 0 ≤ b ≤ m − 1 } ∪ { H Z ( 1 ) } , \mathcal{G} := \left\{H_{ij}^{(b)} = X_i^{(b)}X_j^{(b)} + Y_i^{(b)}Y_j^{(b)} : 0 \le i < j \le n - 1,\ 0 \le b \le m - 1\right\} \cup\left\{H_Z^{(1)}\right\}, G := { H ij ( b ) = X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) : 0 ≤ i < j ≤ n − 1 , 0 ≤ b ≤ m − 1 } ∪ { H Z ( 1 ) } , where H Z ( 1 ) H_Z^{(1)} H Z ( 1 ) is any diagonal excitation-preserving term whose restriction to H 1 \mathcal{H}_1 H 1 is not proportional to the identity. Restricted to the one-excitation sector H 1 = span { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩ } \mathcal{H}_1 = \operatorname{span}\{\lvert e_0\rangle,\ldots,\lvert e_{n-1}\rangle\} H 1 = span {∣ e 0 ⟩ , … , ∣ e n − 1 ⟩} , the dynamical Lie algebra generated by i G i\mathcal{G} i G is s u ( n ) \mathfrak{su}(n) su ( n ) . Consequently, for any V ∈ S U ( n ) V \in\mathrm{SU}(n) V ∈ SU ( n ) and any ε > 0 \varepsilon> 0 ε > 0 there exist angles and a finite product ∏ ℓ = 1 L e − i θ ℓ H α ℓ \prod_{\ell=1}^{L}e^{-i\theta_\ell H_{\alpha_\ell}} ∏ ℓ = 1 L e − i θ ℓ H α ℓ with H α ℓ ∈ G H_{\alpha_\ell} \in\mathcal{G} H α ℓ ∈ G such that
∥ V − ∏ ℓ = 1 L e − i θ ℓ H α ℓ ∥ ≤ ε . \left\|V-\prod_{\ell=1}^{L}e^{-i\theta_\ell H_{\alpha_\ell}}\right\|\le\varepsilon. V − ℓ = 1 ∏ L e − i θ ℓ H α ℓ ≤ ε .
Proof sketch (See App A.4). Work in the one-excitation basis { ∣ e k ⟩ } k = 0 n − 1 \{\lvert e_k\rangle\}_{k=0}^{n-1} {∣ e k ⟩ } k = 0 n − 1 of H 1 \mathcal{H}_1 H 1 . On this sector, each XY coupling acts as a symmetric matrix unit, H i j ∣ H 1 = E i j + E j i H_{ij}|_{\mathcal{H}_1}=E_{ij}+E_{ji} H ij ∣ H 1 = E ij + E j i , while the diagonal excitation-preserving term restricts to a non-scalar diagonal D = H Z ( 1 ) ∣ H 1 = ∑ k d k E k k D=H_Z^{(1)}|_{\mathcal{H}_1}=\sum_k d_kE_{kk} D = H Z ( 1 ) ∣ H 1 = ∑ k d k E k k with D ∝̸ I D\not\propto I D ∝ I . The key observation is that commutators with D D D turn symmetric off-diagonals into skew-symmetric ones: whenever d i ≠ d j d_i\ne d_j d i = d j ,
[ D , E i j + E j i ] = ( d i − d j ) ( E i j − E j i ) , [D,E_{ij}+E_{ji}]=(d_i-d_j)(E_{ij}-E_{ji}), [ D , E ij + E j i ] = ( d i − d j ) ( E ij − E j i ) ,
so the Lie closure contains both E i j + E j i E_{ij}+E_{ji} E ij + E j i and E i j − E j i E_{ij}-E_{ji} E ij − E j i for at least one pair. Commuting these then produces traceless diagonals
[ E i j + E j i , E i j − E j i ] = 2 ( E i i − E j j ) , [E_{ij}+E_{ji},E_{ij}-E_{ji}]=2(E_{ii}-E_{jj}), [ E ij + E j i , E ij − E j i ] = 2 ( E ii − E j j ) ,
and iterating standard bracket identities yields the full space of traceless diagonal operators on H 1 \mathcal{H}_1 H 1 .
Finally, using any traceless diagonal that separates k k k and ℓ \ell ℓ ,
[ E k k − E ℓ ℓ , E k ℓ + E ℓ k ] = 2 ( E k ℓ − E ℓ k ) , [E_{kk}-E_{\ell\ell},E_{k\ell}+E_{\ell k}]=2(E_{k\ell}-E_{\ell k}), [ E k k − E ℓℓ , E k ℓ + E ℓ k ] = 2 ( E k ℓ − E ℓ k ) ,
one obtains skew-symmetric off-diagonals for every ( k , ℓ ) (k,\ell) ( k , ℓ ) . Hence the Lie closure contains the usual spanning set of s u ( n ) \mathfrak{su}(n) su ( n ) given by symmetric off-diagonals, skew-symmetric off-diagonals, and traceless diagonals, so Lie ( i G ) ∣ H 1 = s u ( n ) \operatorname{Lie}(i\mathcal{G})|_{\mathcal{H}_1}=\mathfrak{su}(n) Lie ( i G ) ∣ H 1 = su ( n ) . Standard controllability then implies that products of exp ( − i θ H ) \exp(-i\theta H) exp ( − i θ H ) with H ∈ G H\in\mathcal{G} H ∈ G can approximate any target V ∈ S U ( n ) V\in\mathrm{SU}(n) V ∈ SU ( n ) to arbitrary precision.
Encoded Unitary Designs
Roadmap. In § 2.1 we set up the problem–algorithm co-design and formalized the CE–QAOA kernel , fixing the encoded space, symmetry assumptions, mixer normalization, and initial states. In § 3.1 we show that blockwise label permutations induce an exact unitary 1-design on the encoded space, yielding a clean 1 / D 1/D 1/ D baseline and an averaging-to-existence guarantee for favorable angles (and explaining heavy-output peaks when no twirl is applied). In § 3.2 we lift this to ε \varepsilon ε -approximate 2-design control via per-block XY controllability combined with diagonal cross-block entanglers provides second-moment (anticoncentration) bounds at poly depth. In § 3.3 we benchmark against classical procedures under two ambient domains, isolating the D / S D/S D / S vs. 2 n 2 / S 2^{n^2}/S 2 n 2 / S baselines. and the resulting conditional separation. Finally, §3.4 packages these ingredients into a polytime hybrid quantum–classical (PHQC) solver that couples a coarse ( γ , β ) (\gamma,\beta) ( γ , β ) grid with a deterministic checker, yielding Chernoff-style shot guarantees independent of empirical frequency.
Exact Unitary 1 1 1 -design from block permutation twirl
We now turn to low order moment analysis [20 ] starting from the emergence of exact unitary 1 1 1 design in CE-QAOA. Our kernel (Def. 1 ) explicitly requires that the constraints be exchangeable under block permutations S m S_m S m and symbol relabelings S n S_n S n . This symmetry is a co-design choice that is enforced at the modeling level and then exploited algorithmically contributing a very rich dynamical structure to our formalism. For example, the block Level permutation–twirling action preserves the one-hot condition on the Hilbert space H O H \mathcal{H}_{\mathrm{OH}} H OH (See App. § 6 .§ 1 for a global feasibility preserving permutation). To see this, let
B ≡ S n × m = { P = ⨂ b = 0 m − 1 P b : P b ∈ S n } ⊂ U ( H O H ) , \mathcal{B} \equiv S_n^{\times m} = \left\{P = \bigotimes_{b=0}^{m-1} P_b : P_b \in S_n\right\} \subset U(\mathcal{H}_{\mathrm{OH}}), B ≡ S n × m = { P = b = 0 ⨂ m − 1 P b : P b ∈ S n } ⊂ U ( H OH ) ,
which applies independent label permutations in each block. This action is not feasibility–preserving in general (it can break column one–hot), but it does implement a first–moment (1 1 1 -design) average on the encoded space as an immediate consequence.
Consider a coarse uniform grid search with n + 1 n+1 n + 1 points:
G n + 1 : = { j π n : j = 0 , 1 , … , n } . \mathcal{G}_{n+1} := \left\{\frac{j\pi}{n} : j=0,1,\ldots,n\right\}. G n + 1 := { n j π : j = 0 , 1 , … , n } .
and take γ ∈ G n + 1 \gamma\in\mathcal{G}_{n+1} γ ∈ G n + 1 and β ∈ G n + 1 \beta\in\mathcal{G}_{n+1} β ∈ G n + 1 . Let H ~ M ( b ) \widetilde{H}_M^{(b)} H M ( b ) be the normalized block-XY mixer on the one-excitation subspace. The following existence result holds:
Theorem 13 (Existence of Uniform Overlap Lower Bound via Block Permutations). For any product basis vector ∣ x ⋆ ⟩ ∈ H O H |x^\star\rangle\in\mathcal{H}_{\mathrm{OH}} ∣ x ⋆ ⟩ ∈ H OH , and any angles ( γ , β ) (\gamma,\beta) ( γ , β ) , there exists a blockwise permutation P ⋆ P^\star P ⋆ such that
∣ ⟨ x ⋆ ∣ P ⋆ † U M ( β ) U C ( γ ) s 0 ⟩ ∣ 2 ≥ c n m . \left|\langle x^\star| P^{\star\dagger} U_M(\beta) U_C(\gamma) s_0\rangle\right|^2 \ge\frac{c}{n^m}. ⟨ x ⋆ ∣ P ⋆† U M ( β ) U C ( γ ) s 0 ⟩ 2 ≥ n m c .
To prove this, we shall need two Lemmas.
Lemma 14 (Existence from an average (pigeonhole/averaging principle)). Let { O t } t ∈ T \{O_t\}_{t\in T} { O t } t ∈ T be a finite family of Hermitian operators on any Hilbert space H \mathcal{H} H , and let ρ \rho ρ be any density operator (positive semidefinite, trace 1) on H \mathcal{H} H . Define the arithmetic mean operator
O ‾ : = 1 ∣ T ∣ ∑ t ∈ T O t . \overline{O} := \frac{1}{|T|}\sum_{t\in T} O_t. O := ∣ T ∣ 1 t ∈ T ∑ O t . Then there exists an index t ⋆ ∈ T t^\star\in T t ⋆ ∈ T such that the expectation value of O t ⋆ O_{t^\star} O t ⋆ in the state ρ \rho ρ is at least the expectation value of the mean operator:
Tr ( ρ O t ⋆ ) ≥ Tr ( ρ O ‾ ) . \operatorname{Tr}(\rho O_{t^\star}) \ge\operatorname{Tr}(\rho\overline{O}). Tr ( ρ O t ⋆ ) ≥ Tr ( ρ O ) . i.e. among the set { Tr ( ρ O t ) : t ∈ T } \{\operatorname{Tr}(\rho O_t):t\in T\} { Tr ( ρ O t ) : t ∈ T } at least one is not smaller than their average.
Proof. By linearity of the trace,
1 ∣ T ∣ ∑ t ∈ T Tr ( ρ O t ) = Tr ( ρ 1 ∣ T ∣ ∑ t ∈ T O t ) = Tr ( ρ O ‾ ) . \frac{1}{|T|}\sum_{t\in T}\operatorname{Tr}(\rho O_t)
= \operatorname{Tr}\left(\rho\frac{1}{|T|}\sum_{t\in T}O_t\right)
= \operatorname{Tr}(\rho\overline{O}). ∣ T ∣ 1 t ∈ T ∑ Tr ( ρ O t ) = Tr ( ρ ∣ T ∣ 1 t ∈ T ∑ O t ) = Tr ( ρ O ) . If every Tr ( ρ O t ) \operatorname{Tr}(\rho O_t) Tr ( ρ O t ) were strictly smaller than Tr ( ρ O ‾ ) \operatorname{Tr}(\rho\overline{O}) Tr ( ρ O ) , their average would also be strictly smaller—contradiction. Hence some t ⋆ t^\star t ⋆ attains at least the average.
Lemma 15 (Blockwise twirl (B \mathcal{B} B ) yields the 1 / D 1/D 1/ D baseline). Let H 1 ≅ C n \mathcal{H}_1 \cong\mathbb{C}^n H 1 ≅ C n be the one-hot subspace on a block H 1 \mathcal{H}_1 H 1 . Let the product one-hot subspace be H O H = H 1 ⊗ m \mathcal{H}_{\mathrm{OH}}=\mathcal{H}_1^{\otimes m} H OH = H 1 ⊗ m . So D = dim H O H = n m D=\dim\mathcal{H}_{\mathrm{OH}}=n^m D = dim H OH = n m . For each block b ∈ { 0 , … , m − 1 } b\in\{0,\ldots,m-1\} b ∈ { 0 , … , m − 1 } , let P b P_b P b be a uniformly random permutation matrix acting on { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩ } \{|e_0\rangle,\ldots,|e_{n-1}\rangle\} { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩} and set P : = ⨂ b = 0 m − 1 P b P:=\bigotimes_{b=0}^{m-1}P_b P := ⨂ b = 0 m − 1 P b . Then, for any fixed unitary U U U on H O H \mathcal{H}_{\mathrm{OH}} H OH , any product basis vector ∣ x ⋆ ⟩ |x^\star\rangle ∣ x ⋆ ⟩ , and any state ∣ ϕ ⟩ ∈ H O H |\phi\rangle\in\mathcal{H}_{\mathrm{OH}} ∣ ϕ ⟩ ∈ H OH (all independent of P P P ),
E P [ ∣ ⟨ x ⋆ ∣ P † U ∣ ϕ ⟩ ∣ 2 ] = 1 D . (6) \mathbb{E}_P\left[\left|\langle x^\star|P^\dagger U|\phi\rangle\right|^2\right]=\frac{1}{D}. \tag*{(6)} E P [ ⟨ x ⋆ ∣ P † U ∣ ϕ ⟩ 2 ] = D 1 . (6) Equivalently, at the operator level,
E P [ U † P ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ P † U ] = I D D . (7) \mathbb{E}_P\left[U^\dagger P|x^\star\rangle\langle x^\star|P^\dagger U\right]=\frac{I_D}{D}. \tag*{(7)} E P [ U † P ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ P † U ] = D I D . (7) where I D I_D I D is the identity on H O H \mathcal{H}_{\mathrm{OH}} H OH .
Proof. Write x ⋆ = ( j 0 ⋆ , … , j m − 1 ⋆ ) x^\star=(j_0^\star,\ldots,j_{m-1}^\star) x ⋆ = ( j 0 ⋆ , … , j m − 1 ⋆ ) with ∣ x ⋆ ⟩ = ⨂ b = 0 m − 1 ∣ e j b ⋆ ⟩ |x^\star\rangle=\bigotimes_{b=0}^{m-1}|e_{j_b^\star}\rangle ∣ x ⋆ ⟩ = ⨂ b = 0 m − 1 ∣ e j b ⋆ ⟩ . For a single block b b b , uniform conjugation by P b P_b P b averages a rank-one projector over all basis labels:
E P b [ P b ∣ e j b ⋆ ⟩ ⟨ e j b ⋆ ∣ P b † ] = 1 n ∑ j = 0 n − 1 ∣ e j ⟩ ⟨ e j ∣ = I n n . \mathbb{E}_{P_b}\left[P_b|e_{j_b^\star}\rangle\langle e_{j_b^\star}|P_b^\dagger\right]
=\frac{1}{n}\sum_{j=0}^{n-1}|e_j\rangle\langle e_j|
=\frac{I_n}{n}. E P b [ P b ∣ e j b ⋆ ⟩ ⟨ e j b ⋆ ∣ P b † ] = n 1 j = 0 ∑ n − 1 ∣ e j ⟩ ⟨ e j ∣ = n I n . Independence across blocks gives
E P [ P ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ P † ] = ⨂ b = 0 m − 1 I n n = I D D . \mathbb{E}_P\left[P|x^\star\rangle\langle x^\star|P^\dagger\right]
=\bigotimes_{b=0}^{m-1}\frac{I_n}{n}
=\frac{I_D}{D}. E P [ P ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ P † ] = b = 0 ⨂ m − 1 n I n = D I D . Conjugating by the fixed unitary U U U yields (7) . Taking the expectation value of (7) in the state ∣ ϕ ⟩ |\phi\rangle ∣ ϕ ⟩ gives the scalar identity (6) :
E P [ ∣ ⟨ x ⋆ ∣ P † U ∣ ϕ ⟩ ∣ 2 ] = Tr [ U ∣ ϕ ⟩ ⟨ ϕ ∣ U † I D D ] = 1 D . \mathbb{E}_P\left[\left|\langle x^\star|P^\dagger U|\phi\rangle\right|^2\right]
=\operatorname{Tr}\left[U|\phi\rangle\langle\phi|U^\dagger\frac{I_D}{D}\right]
=\frac{1}{D}. E P [ ⟨ x ⋆ ∣ P † U ∣ ϕ ⟩ 2 ] = Tr [ U ∣ ϕ ⟩ ⟨ ϕ ∣ U † D I D ] = D 1 .
Proof of Thm. 13 . Fix any angles ( γ , β ) (\gamma,\beta) ( γ , β ) and write U : = U M ( β ) U C ( γ ) U := U_M(\beta)U_C(\gamma) U := U M ( β ) U C ( γ ) . Let ρ : = ∣ s 0 ⟩ ⟨ s 0 ∣ \rho:= |s_0\rangle\langle s_0| ρ := ∣ s 0 ⟩ ⟨ s 0 ∣ and, for each blockwise permutation P = ⨁ b = 0 m − 1 P b P = \bigoplus_{b=0}^{m-1} P_b P = ⨁ b = 0 m − 1 P b , define the observable O P : = U † P † ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ P † U O_P := U^\dagger P^\dagger|x^\star\rangle\langle x^\star|P^\dagger U O P := U † P † ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ P † U . By Lemma 15 ,
E P [ O P ] = I D D , D = n m , \mathbb{E}_P[O_P] = \frac{I_D}{D}, \qquad D = n^m, E P [ O P ] = D I D , D = n m ,
and therefore
E P [ Tr ( ρ O P ) ] = Tr ( ρ I D D ) = 1 D . \mathbb{E}_P\left[\operatorname{Tr}(\rho O_P)\right] = \operatorname{Tr}\left(\rho\frac{I_D}{D}\right) = \frac{1}{D}. E P [ Tr ( ρ O P ) ] = Tr ( ρ D I D ) = D 1 .
Applying Lemma 14 (Existence via averaging) to the finite set T = { P } T = \{P\} T = { P } with observables { O P } P ∈ T \{O_P\}_{P\in T} { O P } P ∈ T and state ρ \rho ρ yields the existence of some blockwise permutation P ⋆ P^\star P ⋆ (possibly depending on γ , β , x ⋆ \gamma,\beta,x^\star γ , β , x ⋆ ) such that
∣ ⟨ x ⋆ ∣ P ⋆ † U ∣ s 0 ⟩ ∣ 2 = Tr ( ρ O P ⋆ ) ≥ 1 D = 1 n m . \left|\langle x^\star| P^{\star\dagger}U |s_0\rangle\right|^2 = \operatorname{Tr}(\rho O_{P^\star}) \ge\frac{1}{D} = \frac{1}{n^m}. ⟨ x ⋆ ∣ P ⋆† U ∣ s 0 ⟩ 2 = Tr ( ρ O P ⋆ ) ≥ D 1 = n m 1 .
Corollary 16 (Feasible–optimum specialization of Thm. 13 ). Fix any grid angles ( γ , β ) ∈ G n + 1 × G n + 1 (\gamma,\beta) \in\mathcal{G}_{n+1} \times\mathcal{G}_{n+1} ( γ , β ) ∈ G n + 1 × G n + 1 and set U = U M ( β ) U C ( γ ) U = U_M(\beta)U_C(\gamma) U = U M ( β ) U C ( γ ) on H O H \mathcal{H}_{\mathrm{OH}} H OH with D = dim H O H = n m D = \dim\mathcal{H}_{\mathrm{OH}} = n^m D = dim H OH = n m . Let x ⋆ x^\star x ⋆ be any feasible optimal label. Then there exists a blockwise permutation P ⋆ P^\star P ⋆ such that
∣ ⟨ x ⋆ ∣ P ⋆ † U ∣ s 0 ⟩ ∣ 2 ≥ 1 D = 1 n m . \left|\langle x^\star| P^{\star\dagger}U |s_0\rangle\right|^2 \ge\frac{1}{D} = \frac{1}{n^m}. ⟨ x ⋆ ∣ P ⋆† U ∣ s 0 ⟩ 2 ≥ D 1 = n m 1 . In particular, the constant in Theorem 13 can be taken as c = 1 c = 1 c = 1 .
Proof. Theorem 13 holds for any product basis vector x ⋆ ∈ H O H x^\star\in\mathcal{H}_{\mathrm{OH}} x ⋆ ∈ H OH . It also holds for any grid angles ( γ , β ) ∈ G n + 1 × G n + 1 (\gamma,\beta) \in\mathcal{G}_{n+1} \times\mathcal{G}_{n+1} ( γ , β ) ∈ G n + 1 × G n + 1 . Finally, choosing x ⋆ x^\star x ⋆ to be any feasible optimum preserves the bound. Hence the inequality holds with c = 1 c = 1 c = 1 .
Lemmas 14–15 establish a permutation–twirl control: for any fixed U U U on H O H \mathcal{H}_{\mathrm{OH}} H OH and any label ∣ x ⟩ |x\rangle ∣ x ⟩ , the averaged success probability equals the 1 / D 1/D 1/ D baseline. This identity certifies that random relabeling erases instance structure but offers a robust theoretical floor. For fixed angles U : = U M ( β ) U C ( γ ) U := U_M(\beta)U_C(\gamma) U := U M ( β ) U C ( γ ) and target ∣ x ⋆ ⟩ |x^\star\rangle ∣ x ⋆ ⟩ , define
p γ , β x ⋆ ( P ) : = ∣ ⟨ x ⋆ ∣ P † U ∣ s 0 ⟩ ∣ 2 . p_{\gamma,\beta}^{x^\star}(P) := \left|\langle x^\star| P^\dagger U |s_0\rangle\right|^2. p γ , β x ⋆ ( P ) := ⟨ x ⋆ ∣ P † U ∣ s 0 ⟩ 2 .
The blockwise permutation twirl gives the control identity E P [ p γ , β x ⋆ ( P ) ] = 1 / D \mathbb{E}_P[p_{\gamma,\beta}^{x^\star}(P)] = 1/D E P [ p γ , β x ⋆ ( P )] = 1/ D . Hence the native labeling P = i d P = \mathrm{id} P = id realizes one point in this distribution and, by averaging, there must exist labelings with p γ , β x ⋆ ( P ) > 1 / D p_{\gamma,\beta}^{x^\star}(P) > 1/D p γ , β x ⋆ ( P ) > 1/ D and others with < 1 / D < 1/D < 1/ D . Running the circuit without random per-shot relabelings (i.e., without implementing the twirl) samples p γ , β x ⋆ ( i d ) p_{\gamma,\beta}^{x^\star}(\mathrm{id}) p γ , β x ⋆ ( id ) , which can be strictly larger than 1 / D 1/D 1/ D whenever the angles and the instance structure produce constructive interference for the native labels. This arises when energetically favored blocks capture probability mass above the 1 / n 1/n 1/ n average. Empirically this appears as peaks for the optimum/near-optimum bars that lie well above the dashed 1 / D 1/D 1/ D line (cf. Figure 4 ).
Figure 4. Single Layer CE-QAOA circuits on noiseless Aer simulator [52 ] on two TSP instances (wi5 (25 qubits) and wi6 (36 qubits)) taken from QOptLib benchmark set [30 ] . Histograms show the counts of feasible bit-strings (permutation indices) out of 50 × n 4 50 \times n^4 50 × n 4 shots for a problem of size n n n locations. The green bars mark two degenerate best tours. Several grid points already identify the optimum with nontrivial probability well above the lower bound. The dashed line marks the 1 / D 1/D 1/ D baseline with D = n n D = n^n D = n n . The purple bars show when the best bitsring is also the most frequent.
By contrast, applying random blockwise permutations per shot flattens the histogram toward the 1 / D 1/D 1/ D control and typically reduces such peaks. Thus non-twirled sampling is the appropriate mode for optimization (preserves useful bias), while twirling serves as a null/control for analytical bounds rather than a performance booster. Consequently, we optimize in the native labeling (no twirl) and interpret any deviation p i d ( x ) − 1 / D p_{\mathrm{id}}(x) - 1/D p id ( x ) − 1/ D as certified problem-induced bias. The practical value of such bias is quantified by shot complexity: if the optimal label satisfies p ⋆ = α / D p_\star= \alpha/D p ⋆ = α / D with α > 1 \alpha> 1 α > 1 , the shots required to observe it with high probability shrink by the same factor. The following corollary holds.
Corollary 17 (Shot complexity gain from heavy outputs). Let p ⋆ : = p i d ( x ⋆ ) p_\star:= p_{\mathrm{id}}(x^\star) p ⋆ := p id ( x ⋆ ) for the optimal label x ⋆ x^\star x ⋆ at some grid point ( γ , β ) (\gamma,\beta) ( γ , β ) . With S S S shots, the failure probability to observe x ⋆ x^\star x ⋆ at least once is ( 1 − p ⋆ ) S ≤ e − p ⋆ S (1-p_\star)^S \le e^{-p_\star S} ( 1 − p ⋆ ) S ≤ e − p ⋆ S . To achieve success probability ≥ 1 − δ \ge1-\delta ≥ 1 − δ it suffices that
S ≥ ln ( 1 / δ ) p ⋆ . S \ge\frac{\ln(1/\delta)}{p_\star}. S ≥ p ⋆ ln ( 1/ δ ) . At the permutation twirling baseline p ⋆ = 1 / D p_\star= 1/D p ⋆ = 1/ D , this is S = Θ ( D log ( 1 / δ ) ) S = \Theta(D\log(1/\delta)) S = Θ ( D log ( 1/ δ )) . Any heavy-output bias p ⋆ = c / D p_\star= c/D p ⋆ = c / D with c > 1 c>1 c > 1 yields an c c c -fold reduction in shots. If p ⋆ ≥ n − k p_\star\ge n^{-k} p ⋆ ≥ n − k for some fixed k k k while D = n m D = n^m D = n m (with m = n m=n m = n in TSP encodings), then S = O ~ ( n k ) S = \widetilde{O}(n^k) S = O ( n k ) versus Ω ~ ( n m ) \widetilde{\Omega}(n^m) Ω ( n m ) at baseline. See Lemma 24 , Thm. 25 and Alg. 4. The two flavors of computational advantages arising from our proposals are discussed in § 3.3 and 4.3. An illustration of the effects of heavy outputs on success probability is shown in Figure 3 [31 ] .3
Figure 3. Heavy outputs vs. baselines. The red dotted line is the twirling baseline of E ∣ ⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 = 1 / D \mathbb{E}\lvert\langle x\lvert U\lvert\phi\rangle\rvert^2 = 1/D E ∣⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 = 1/ D . The light yellow region denotes E ∣ ⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 > c / D \mathbb{E}\lvert\langle x\lvert U\lvert\phi\rangle\rvert^2 > c/D E ∣⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 > c / D existence results from Thm. 13 and Cor. 16. The green region indicate E ∣ ⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 ≈ n − k \mathbb{E}\lvert\langle x\lvert U\lvert\phi\rangle\rvert^2 \approx n^{-k} E ∣⟨ x ∣ U ∣ ϕ ⟩ ∣ 2 ≈ n − k for a fixed constant k k k . Here we write the constant numerator in Thm. 13 c c c as c ( n ) c(n) c ( n ) to emphasize that it is instance dependent. It becomes large when constructive interference arises in absence of the permutation twirling. These higher values overlap with n − k n^{-k} n − k region shaded in green. If the probability of the optimum approaches n − k n^{-k} n − k , then to achieve success probability ≥ 1 − δ \ge1-\delta ≥ 1 − δ it suffices that S ≥ ln ( 1 / δ ) p ⋆ S \ge\frac{\ln(1/\delta)}{p_\star} S ≥ p ⋆ l n ( 1/ δ ) as outline in Cor. 17 . Our simulation results with ln ( 1 / δ ) = 10 \ln(1/\delta)=10 ln ( 1/ δ ) = 10 is reported in Figure 5 where the instance dependent heavy outputs lead to overlap probabilities in the shaded green region.
Remarks on the [ 0 , π ] 2 [0,\pi]^2 [ 0 , π ] 2 window. We use a π \pi π -sized search box in Thm. 13 and the accompanying twirling analyses purely for coverage . The t ∈ { 1 , 2 } t \in\{1,2\} t ∈ { 1 , 2 } moment guarantees (perm-twirl and shallow anticoncentration) only require angles drawn from a constant-size set and do not strengthen by widening the range. Empirically, [ 0 , π ] 2 [0,\pi]^2 [ 0 , π ] 2 balances exploration of distinct phase patterns with modest grid sizes. Noiseless simulation results on Qiskit Aer are reported in Figure 4 to demonstrate this.
To conclude on the emergence of exact unitary 1-design in our formalism, recall that an ensemble { p i , U i } ⊂ U ( d ) \{p_i, U_i\} \subset U(d) { p i , U i } ⊂ U ( d ) is a unitary 1-design if its first-moment (twirling) channel
Φ 1 s t ( X ) : = ∑ i p i ( U i ) X ( U i † ) \Phi_{\mathrm{1st}}(X) := \sum_i p_i (U_i) X (U_i^\dagger) Φ 1st ( X ) := i ∑ p i ( U i ) X ( U i † )
agrees with the Haar first moment Φ H a a r ( 1 ) ( X ) : = ∫ H a a r ( U ) X ( U † ) d U \Phi_{\mathrm{Haar}}^{(1)}(X) := \int_{\mathrm{Haar}} (U) X (U^\dagger)\,\mathrm{d}U Φ Haar ( 1 ) ( X ) := ∫ Haar ( U ) X ( U † ) d U for all X X X on C d \mathbb{C}^d C d . It is an ε \varepsilon ε -approximate 1-design if ∥ Φ 1 s t − Φ H a a r ( 1 ) ∥ ≤ ε \lVert\Phi_{\mathrm{1st}}-\Phi_{\mathrm{Haar}}^{(1)}\rVert\leq\varepsilon ∥ Φ 1st − Φ Haar ( 1 ) ∥ ≤ ε in diamond (or operator) norm. Thus, the identity proved in Lemma 15 is an exact 1-design identity with ε = 0 \varepsilon= 0 ε = 0 . This is a consequence of the block–XY mixer acting as coherent hops between labels inside the H 1 \mathcal{H}_1 H 1 subspace. In the encoded n n n -level (qudit) picture, these hops are realized coherently by the unitary operator, e − i β A ( K n ) e^{-i\beta A(K_n)} e − i β A ( K n ) , where A ( K n ) A(K_n) A ( K n ) is the adjacency of the complete graph on n n n nodes (See Def. 9 and Prop. 10) and any blockwise permutation operator respects this symmetry. Further t t t -unitary design details are available for example in Ref. [20 ] .
ε-approximate unitary 2- designs
Similarly to the 1-design notion, an ensemble { p i , U i } ⊂ U ( d ) \{p_i, U_i\} \subset U(d) { p i , U i } ⊂ U ( d ) is a unitary 2-design if its second-moment (twirling) channel
Φ 2 n d ( X ) : = ∑ i p i ( U i ⊗ U i ) X ( U i † ⊗ U i † ) \Phi_{\mathrm{2nd}}(X) := \sum_i p_i (U_i \otimes U_i) X (U_i^\dagger\otimes U_i^\dagger) Φ 2nd ( X ) := i ∑ p i ( U i ⊗ U i ) X ( U i † ⊗ U i † )
agrees with the Haar second moment Φ H a a r ( 2 ) ( X ) : = ∫ H a a r ( U ⊗ U ) X ( U † ⊗ U † ) d U \Phi_{\mathrm{Haar}}^{(2)}(X) := \int_{\mathrm{Haar}} (U \otimes U) X (U^\dagger\otimes U^\dagger)\,\mathrm{d}U Φ Haar ( 2 ) ( X ) := ∫ Haar ( U ⊗ U ) X ( U † ⊗ U † ) d U for all X X X on C d ⊗ C d \mathbb{C}^d \otimes\mathbb{C}^d C d ⊗ C d . It is an ε \varepsilon ε -approximate 2-design if ∥ Φ 2 n d − Φ H a a r ( 2 ) ∥ ≤ ε \lVert\Phi_{\mathrm{2nd}}-\Phi_{\mathrm{Haar}}^{(2)}\rVert\leq\varepsilon ∥ Φ 2nd − Φ Haar ( 2 ) ∥ ≤ ε in diamond (or operator) norm. In our formalism, if on each block’s one-excitation space H 1 ≅ C n \mathcal{H}_1 \cong\mathbb{C}^n H 1 ≅ C n , we form the local ensemble by applying random XY edge pulses, i.e., layers that choose pairs ( i , j ) (i,j) ( i , j ) and angles θ \theta θ and apply exp ( − i θ ( X i X j + Y i Y j ) ) \exp(-i\theta(X_iX_j + Y_iY_j)) exp ( − i θ ( X i X j + Y i Y j )) . Varying the edges and angles yields a (controllable) gate set whose dynamical Lie algebra is s u ( n ) \mathfrak{su}(n) su ( n ) (Prop. 12 ). So by local random-circuit design results[20 ] , a circuit of length L = poly ( n ) ⋅ polylog ( 1 / ε ) L = \operatorname{poly}(n)\cdot\operatorname{polylog}(1/\varepsilon) L = poly ( n ) ⋅ polylog ( 1/ ε ) forms an ε \varepsilon ε -approximate unitary 2-design on U ( n ) U(n) U ( n ) . We capture this result in the following proposition.
Proposition 18 (Per-block ε \varepsilon ε -approximate 2-design). Recall controllability and approximate universality on H 1 \mathcal{H}_1 H 1 (Prop. 12 ). Let U U U be generated by XY pulses exp ( − i θ ( X i X j + Y i Y j ) ) \exp(-i\theta(X_iX_j + Y_iY_j)) exp ( − i θ ( X i X j + Y i Y j )) and Z Z Z phases exp ( − i φ Z k ) \exp(-i\varphi Z_k) exp ( − i φ Z k ) , with ( θ , φ ) (\theta,\varphi) ( θ , φ ) drawn from bounded continuous densities. On H 1 \mathcal{H}_1 H 1 , a random circuit of length poly ( n ) ⋅ polylog ( 1 / ε ) \operatorname{poly}(n)\cdot\operatorname{polylog}(1/\varepsilon) poly ( n ) ⋅ polylog ( 1/ ε ) sampled from U U U forms an ε \varepsilon ε -approximate unitary 2-design [20 ] .
Interleaving such per-block layers with the diagonal, instance-dependent phase U C ( γ ) U_C(\gamma) U C ( γ ) which is entangling across blocks is needed to promote the product of per-block designs to a global ε g l o b \varepsilon_{\mathrm{glob}} ε glob -approximate unitary 2-design on the encoded space in depth poly ( m , n , log ( 1 / ε g l o b ) ) \operatorname{poly}(m,n,\log(1/\varepsilon_{\mathrm{glob}})) poly ( m , n , log ( 1/ ε glob )) .
In the CE-QAOA kernel (Def. 1 ), each phase layer is generated by a diagonal Hamiltonian in the computational basis which is entangling across blocks due to the global pattern symmetries. With block labels z = ( j 0 , … , j m − 1 ) \mathbf{z}=(j_0,\ldots,j_{m-1}) z = ( j 0 , … , j m − 1 ) , U C ( γ ) U_C(\gamma) U C ( γ ) factorizes over blocks (and thus non-entangling across blocks) iff
C ( j 0 , … , j m − 1 ) = ∑ b = 0 m − 1 c b ( j b ) for some c b : [ n ] → R . (8) C(j_0,\ldots,j_{m-1})=\sum_{b=0}^{m-1}c_b(j_b)\quad\text{for some }c_b:[n]\to\mathbb{R}. \tag*{(8)} C ( j 0 , … , j m − 1 ) = b = 0 ∑ m − 1 c b ( j b ) for some c b : [ n ] → R . (8)
Proposition 19 (Diagonal entangler criterion). For two blocks b ≠ b ′ b\ne b' b = b ′ , restrict C C C to C b , b ′ ( j , k ) C_{b,b'}(j,k) C b , b ′ ( j , k ) with other labels fixed and consider
U b , b ′ ( γ ) = ∑ j , k = 0 n − 1 e − i γ C b , b ′ ( j , k ) ∣ j ⟩ ⟨ j ∣ ⊗ ∣ k ⟩ ⟨ k ∣ . U_{b,b'}(\gamma)=\sum_{j,k=0}^{n-1}e^{-i\gamma C_{b,b'}(j,k)}|j\rangle\langle j|\otimes|k\rangle\langle k|. U b , b ′ ( γ ) = j , k = 0 ∑ n − 1 e − iγ C b , b ′ ( j , k ) ∣ j ⟩ ⟨ j ∣ ⊗ ∣ k ⟩ ⟨ k ∣. The operator–Schmidt rank of U b , b ′ ( γ ) U_{b,b'}(\gamma) U b , b ′ ( γ ) exceeds 1 (hence the gate is entangling) unless there exist functions α ( j ) \alpha(j) α ( j ) , β ( k ) \beta(k) β ( k ) and a phase θ \theta θ with e − i γ C b , b ′ ( j , k ) = e − i θ a ( j ) b ( k ) e^{-i\gamma C_{b,b'}(j,k)}=e^{-i\theta}a(j)b(k) e − iγ C b , b ′ ( j , k ) = e − i θ a ( j ) b ( k ) for all j , k j,k j , k , i.e. unless C b , b ′ ( j , k ) = α ( j ) + β ( k ) C_{b,b'}(j,k)=\alpha(j)+\beta(k) C b , b ′ ( j , k ) = α ( j ) + β ( k ) modulo 2 π / γ 2\pi/\gamma 2 π / γ . Equivalently, the diagonal two-qudit gate has operator–Schmidt rank > 1 >1 > 1 iff the matrix M j k = e − i γ C b , b ′ ( j , k ) M_{jk}=e^{-i\gamma C_{b,b'}(j,k)} M j k = e − iγ C b , b ′ ( j , k ) has rank > 1 >1 > 1 .
Proof. For a diagonal two-qudit operator, the operator–Schmidt rank equals the rank of the matrix M j k = e − i γ C b , b ′ ( j , k ) M_{jk}=e^{-i\gamma C_{b,b'}(j,k)} M j k = e − iγ C b , b ′ ( j , k ) . Rank 1 holds iff M j k = a ( j ) b ( k ) M_{jk}=a(j)b(k) M j k = a ( j ) b ( k ) .
Global constraints in typical COPs (TSP/VRP, assignment, capacity/balance) introduce cross-block couplings, so U C ( γ ) U_C(\gamma) U C ( γ ) is generically entangling on ( C n ) ⊗ m (\mathbb{C}^{n})^{\otimes m} ( C n ) ⊗ m . We can therefore combine it with short, per-block 2-designs to obtain strong second-moment mixing on the encoded space. To that end, we partition the diagonal generator as
H C = H o b j + H p e n . H_C=H_{\mathrm{obj}}+H_{\mathrm{pen}}. H C = H obj + H pen .
with the following roles. (i) H o b j H_{\mathrm{obj}} H obj is diagonal and, upon restriction to a single block, provides sufficiently rich on-block phases so that, together with XY hops inside the block, the Lie algebra on H 1 ≃ C n \mathcal{H}_1\simeq\mathbb{C}^{n} H 1 ≃ C n is u ( n ) \mathfrak{u}(n) u ( n ) . (These on-block phases may be present explicitly or synthesized via standard refocusing.) (ii) H p e n H_{\mathrm{pen}} H pen is diagonal and cross-block . It contains at least one non-additive term across some pair b ≠ b ′ b\ne b' b = b ′ , so that for fixed spectators the induced table C b , b ′ ( j , k ) C_{b,b'}(j,k) C b , b ′ ( j , k ) fails C b , b ′ ( j , k ) = α ( j ) + β ( k ) C_{b,b'}(j,k)=\alpha(j)+\beta(k) C b , b ′ ( j , k ) = α ( j ) + β ( k ) . By Prop. 19 , e − i γ H p e n e^{-i\gamma H_{\mathrm{pen}}} e − iγ H pen is then entangling across blocks. (Equivalently, the matrix M j k = e − i γ C b , b ′ ( j , k ) M_{jk}=e^{-i\gamma C_{b,b'}(j,k)} M j k = e − iγ C b , b ′ ( j , k ) has rank > 1 >1 > 1 .)
If each block ensemble is an ε \varepsilon ε -approximate unitary 2-design on U ( n ) U(n) U ( n ) , then the product ensemble on U ( n ) ⊗ m U(n)^{\otimes m} U ( n ) ⊗ m reproduces the Haar second moments of degree-≤ 2 \le2 ≤ 2 polynomials with error O ( m ε ) O(m\varepsilon) O ( m ε ) .
Theorem 20 (Global ε g l o b \varepsilon_{\mathrm{glob}} ε glob -approximate unitary 2 2 2 -design (mild randomness)). Assume the block–interaction graph induced by H p e n H_{\mathrm{pen}} H pen is connected and that either (i) the phases γ ℓ \gamma_\ell γ ℓ are i.i.d. from a bounded continuous density, or (ii) the set of coupled block pairs in H p e n H_{\mathrm{pen}} H pen is chosen i.i.d. each layer from a distribution with full support on the edges of the graph. Then there exists
L = poly ( m , n , log ( 1 / ε g l o b ) ) L = \operatorname{poly}(m,n,\log(1/\varepsilon_{\mathrm{glob}})) L = poly ( m , n , log ( 1/ ε glob )) s.t. the distribution of U L = L L ⋯ L 1 U_L = \mathcal{L}_L \cdots\mathcal{L}_1 U L = L L ⋯ L 1 is an ε g l o b \varepsilon_{\mathrm{glob}} ε glob -approximate unitary 2 2 2 -design on U ( n m ) U(n^m) U ( n m ) .
Proof. Setup: Consider alternating layers on ( C n ) ⊗ m (\mathbb{C}^n)^{\otimes m} ( C n ) ⊗ m
L ℓ = ( ⨂ b = 0 m − 1 R b ( ℓ ) ) e − i γ ℓ H p e n , ℓ = 1 , … , L , (9) \mathcal{L}_\ell= \left(\bigotimes_{b=0}^{m-1} R_b^{(\ell)}\right)e^{-i\gamma_\ell H_{\mathrm{pen}}}, \qquad\ell=1,\ldots,L, \tag*{(9)} L ℓ = ( b = 0 ⨂ m − 1 R b ( ℓ ) ) e − i γ ℓ H pen , ℓ = 1 , … , L , (9)
where each R b ( ℓ ) R_b^{(\ell)} R b ( ℓ ) is drawn independently from a per-block ε \varepsilon ε -approximate 2 2 2 -design and e − i γ ℓ H p e n e^{-i\gamma_\ell H_{\mathrm{pen}}} e − i γ ℓ H pen is an entangling diagonal gate across blocks (Prop. 19 ). Assume a mild randomness on the penalty layer and fix one layer L ℓ = ⨂ b R b ( ℓ ) e − i γ ℓ H p e n \mathcal{L}_\ell= \bigotimes_b R_b^{(\ell)}e^{-i\gamma_\ell H_{\mathrm{pen}}} L ℓ = ⨂ b R b ( ℓ ) e − i γ ℓ H pen . For t = 2 t=2 t = 2 moments, analyze the superoperator E [ U ⊗ 2 ⊗ U ‾ ⊗ 2 ] \mathbb{E}\left[U^{\otimes2} \otimes\overline{U}^{\otimes2}\right] E [ U ⊗ 2 ⊗ U ⊗ 2 ] of the depth-L L L circuit.
(1) Local twirl to { I , S W A P } \{I,\mathrm{SWAP}\} { I , SWAP } . Each R b ( ℓ ) R_b^{(\ell)} R b ( ℓ ) is drawn from a per-block ε \varepsilon ε -approximate 2 2 2 -design, so its second-moment twirl projects (up to O ( ε ) O(\varepsilon) O ( ε ) ) any operator on the two-copy space of block b b b onto the commutant of U ( n ) U(n) U ( n ) , i.e. the span of { I b , S W A P b } \{I_b,\mathrm{SWAP}_b\} { I b , SWAP b } . Thus, after averaging over the R b ( ℓ ) R_b^{(\ell)} R b ( ℓ ) , the state space relevant to second moments reduces to a classical spin system on m m m sites with local alphabet { I , S W A P } \{I,\mathrm{SWAP}\} { I , SWAP } .
(2) Effect of the entangling diagonal. Consider an edge ( b , b ′ ) (b,b') ( b , b ′ ) coupled by a term in H p e n H_{\mathrm{pen}} H pen . Conjugation by e − i γ ℓ H p e n e^{-i\gamma_\ell H_{\mathrm{pen}}} e − i γ ℓ H pen , restricted to this edge and then followed by the local twirls from step (1), induces a stochastic update on the pair ( { I , S W A P } b , { I , S W A P } b ′ ) (\{I,\mathrm{SWAP}\}_b,\{I,\mathrm{SWAP}\}_{b'}) ({ I , SWAP } b , { I , SWAP } b ′ ) that is nontrivial whenever the two-block phase table C b , b ′ ( j , k ) C_{b,b'}(j,k) C b , b ′ ( j , k ) is non-additive (Prop. 19 ). Hence each coupled edge implements a mixing step on the reduced alphabet.
(3) Ergodicity and spectral gap (Cf. Prop. 8). Assume the block–interaction graph of H p e n H_{\mathrm{pen}} H pen is connected and that, per layer, either the coupled edge or the phase parameter is drawn from a distribution with full support. Then the induced Markov chain on { I , S W A P } m \{I,\mathrm{SWAP}\}^m { I , SWAP } m is irreducible and aperiodic, with a spectral gap bounded below by Ω ( 1 / poly ( m ) ) \Omega(1/\operatorname{poly}(m)) Ω ( 1/ poly ( m )) . Consequently the product of L = poly ( m , n ) polylog ( 1 / ε g l o b ) L=\operatorname{poly}(m,n)\operatorname{polylog}(1/\varepsilon_{\mathrm{glob}}) L = poly ( m , n ) polylog ( 1/ ε glob ) such layers converges to the unique fixed point, which coincides with the global Haar second moment on ( C n ) ⊗ m (\mathbb{C}^n)^{\otimes m} ( C n ) ⊗ m (up to the usual O ( ε ) O(\varepsilon) O ( ε ) error from the local designs).
(4) In conclusion, this is exactly the t = 2 t=2 t = 2 instance of the Brandão–Harrow–Horodecki random-circuit mixing framework[20 ] , with the qudit case handled by the same moment–operator gap argument[55 ] .4
Corollary 21 (Constant-measure good angles under a 2 2 2 -design). *Let U U U be an ε \varepsilon ε -approximate unitary 2 2 2 -design on the encoded space (e.g., as in Thm. 20 ). For fixed x ⋆ x^\star x ⋆ and input ∣ ϕ ⟩ |\phi\rangle ∣ ϕ ⟩ , with X = ∣ ⟨ x ⋆ ∣ U ∣ ϕ ⟩ ∣ 2 X = | \langle x^\star|U|\phi\rangle|^2 X = ∣ ⟨ x ⋆ ∣ U ∣ ϕ ⟩ ∣ 2 where U ∼ U U\sim U U ∼ U ,
E [ X ] = 1 D ± O ( ε ) , E [ X 2 ] = 2 D ( D + 1 ) ± O ( ε ) 5 , \mathbb{E}[X] = \frac{1}{D} \pm O(\varepsilon), \qquad\mathbb{E}[X^2] = \frac{2}{D(D+1)} \pm O(\varepsilon)^5, E [ X ] = D 1 ± O ( ε ) , E [ X 2 ] = D ( D + 1 ) 2 ± O ( ε ) 5 ,
M 2 = E [ U ⊗ 2 ⊗ U ‾ ⊗ 2 ] , M_2 = \mathbb{E}\left[U^{\otimes2} \otimes\overline{U}^{\otimes2}\right], M 2 = E [ U ⊗ 2 ⊗ U ⊗ 2 ] ,
or equivalently, after local twirling, to the spectral gap of the induced Markov kernel on the reduced commutant basis { I , S W A P } m \{I,\mathrm{SWAP}\}^m { I , SWAP } m ; this gap controls the exponential convergence of M 2 L M_2^L M 2 L to the Haar second moment [20 , 55 ] . See App. § 6 .§ 5 . and Paley–Zygmund gives Pr [ X ≥ 1 2 D ] ≥ ( D + 1 ) / ( 8 D ) − O ( ε ) = Ω ( 1 ) \Pr[X \ge\frac{1}{2D}] \ge(D+1)/(8D) - O(\varepsilon) = \Omega(1) Pr [ X ≥ 2 D 1 ] ≥ ( D + 1 ) / ( 8 D ) − O ( ε ) = Ω ( 1 ) . Thus, Paley–Zygmund gives, for sufficiently small ε g l o b \varepsilon_{\mathrm{glob}} ε glob ,
Pr [ X ≥ 1 2 D ] ≥ ( E [ X ] − 1 2 D ) 2 E [ X 2 ] ≳ ( 1 / 2 D ) 2 2 / ( D ( D + 1 ) ) = D + 1 8 D = Ω ( 1 ) . (10) \Pr\left[X \ge\frac{1}{2D}\right] \ge\frac{\left(\mathbb{E}[X]-\frac{1}{2D}\right)^2}{\mathbb{E}[X^2]} \gtrsim\frac{(1/2D)^2}{2/(D(D+1))} = \frac{D+1}{8D} = \Omega(1). \tag*{(10)} Pr [ X ≥ 2 D 1 ] ≥ E [ X 2 ] ( E [ X ] − 2 D 1 ) 2 ≳ 2/ ( D ( D + 1 )) ( 1/2 D ) 2 = 8 D D + 1 = Ω ( 1 ) . (10)
Design bounds as controls: Unitary 1-designs vs Unitary 2-designs. Unitary 1-designs give means while unitary 2-designs add dispersion and correlation control and calibrate pairwise covariances of quadratic observables. In combinatorial optimization this means we can quantify anticoncentration within the encoded space; and separate genuine instance–parameter structure (like persistent peaks above 1 / D 1/D 1/ D ) from labeling artifacts. In variational training, 2-design control on second moments stabilizes the statistics of loss estimates (and common gradient/finite-difference estimators that depend on degree-≤ 2 \le2 ≤ 2 unitary moments), yielding instance–size predictable variance and thus shot requirements. For our constraint-enhanced QAOA, the 1-design perspective explains why favorable parameters must exist (and provides a clean null/control), whereas the 2-design refinement explains how reliably we can find and certify them.
Finally, a caveat. Unitary t t t -design bounds (including our 1– and per-block 2-design controls) are conservative : they certify correct means/second moments under structured randomization, but they do not translate into tight, instance-specific shot complexity. In particular, the 1-design baseline 1 / D 1/D 1/ D is an analytic null —useful for existence and for flattening controls via twirls—but it grossly overestimates the shots needed when constructive interference lifts the success probability well above 1 / D 1/D 1/ D . Likewise, second-moment control (O ( m ε ) O(m\varepsilon) O ( m ε ) product moments) stabilizes estimators and separates signal from labeling artifacts, yet it is not a substitute for the binomial tails of the actual success rate p ( γ , β ) p(\gamma,\beta) p ( γ , β ) attained by CE–QAOA at good angles. For shot complexity we therefore appeal to the realized Bernoulli scaling N = O ~ ( 1 / p ⋆ ) N = \widetilde{O}(1/p_\star) N = O ( 1/ p ⋆ ) (via Chernoff (Lemma 24 )), where in our setting p ⋆ p_\star p ⋆ empirically behaves like n − k n^{-k} n − k once only k ≪ m k \ll m k ≪ m blocks remain unaligned. This yields polynomial shot budgets, in stark contrast to the exponential Θ ( D ) \Theta(D) Θ ( D ) implicit in the 1-design null (Cf. Classical competitiveness in § 3.3 vs. Sec 4.3).
Classical Competitiveness I: The Unitary t-Design Baseline
The comparison with classical procedures hinges on what domain the classical sampler can efficiently prepare . Our CE–QAOA acts inside the encoded one-hot product space H O H = [ n ] m \mathcal{H}_{\mathrm{OH}} = [n]^m H OH = [ n ] m of size D = n m D = n^m D = n m . A classical algorithm, however, may or may not have an efficient generator for H O H \mathcal{H}_{\mathrm{OH}} H OH . We therefore separate two information models and stay strictly within first/second moment reasoning where permutation twirls achieve overlap at least 1 / D 1/D 1/ D . Throughout, let F ⊆ H O H F \subseteq\mathcal{H}_{\mathrm{OH}} F ⊆ H OH be the feasible set, ∣ F ∣ = S |F| = S ∣ F ∣ = S , and let U U U be the depth-p p p CE–QAOA circuit restricted to the encoded space. We now make the “ambient domain” explicit.
Model A (structured domain). Both quantum and classical procedures can sample arbitrarily from the encoded domain H O H = [ n ] m \mathcal{H}_{\mathrm{OH}} = [n]^m H OH = [ n ] m (size D = n m D = n^m D = n m ), and both have an oracle answering feasibility membership in F F F .
Model B (raw bitstrings only). The classical procedure sees only raw bitstrings of length N N N (for TSP/assignment, N = n 2 N = n^2 N = n 2 ) and has access to a feasibility predicate f e a s ( z ) ∈ { 0 , 1 } \mathrm{feas}(z) \in\{0,1\} feas ( z ) ∈ { 0 , 1 } that recognizes whether a bitstring encodes a feasible element of F ⊆ H O H F \subseteq\mathcal{H}_{\mathrm{OH}} F ⊆ H OH . No efficient generator for H O H \mathcal{H}_{\mathrm{OH}} H OH is assumed. The quantum procedure, by construction, prepares superpositions inside H O H \mathcal{H}_{\mathrm{OH}} H OH .
Proposition 22 (Model A: matching Θ ( D / S ) \Theta(D/S) Θ ( D / S ) baselines). Suppose both sides can sample uniformly from H O H \mathcal{H}_{\mathrm{OH}} H OH and query feas. Then any classical algorithm that draws i.i.d. proposals from H O H \mathcal{H}_{\mathrm{OH}} H OH has success probability S / D S/D S / D per trial, so the expected number of trials to hit F F F is D / S D/S D / S . For CE–QAOA with a random twirl, Lemma 15 implies the same expected success S / D S/D S / D for “hit any feasible”, hence the same D / S D/S D / S expected trials.
Proposition 23 (Model B: raw-bitstring baseline). Let the classical ambient space be { 0 , 1 } N \{0,1\}^{N} { 0 , 1 } N with N = n 2 N=n^2 N = n 2 (for n = m n=m n = m ), of size 2 N 2^N 2 N , and assume only the feasibility predicate feas is available. Under the minimax distribution in which F F F is uniform among all S S S -subsets of { 0 , 1 } N \{0,1\}^{N} { 0 , 1 } N , the expected number of feasibility queries until the first hit is
E [ # q u e r i e s ] = 2 N + 1 S + 1 = Θ ( 2 n 2 S ) . \mathbb{E}[\#\mathrm{queries}] = \frac{2^N+1}{S+1} = \Theta\left(\frac{2^{n^2}}{S}\right). E [ # queries ] = S + 1 2 N + 1 = Θ ( S 2 n 2 ) . In contrast, CE–QAOA prepares states inside H O H \mathcal{H}_{\mathrm{OH}} H OH and, with only the first-moment guarantee, has expected trials D / S = Θ ( n n / S ) D/S=\Theta(n^n/S) D / S = Θ ( n n / S ) . Thus the ratio of classical (Model B) to quantum expected trials scales like
2 n 2 / S n n / S = 2 n 2 n n = ( 2 n 2 / n n ) n = exp ( Θ ( n 2 ) ) . \frac{2^{n^2}/S}{n^n/S} = \frac{2^{n^2}}{n^n} = \left(\frac{2^{n^2/n}}{n}\right)^n = \exp(\Theta(n^2)). n n / S 2 n 2 / S = n n 2 n 2 = ( n 2 n 2 / n ) n = exp ( Θ ( n 2 )) .
Thus, CE–QAOA already achieves a conditional quantum-classical separation from design only bounds. However, we as we have already discussed, this is a mere theoretical floor independent of constructive interference present when the twirls are not implemented. As we saw in Figure 2 , when the twirling is omitted, heavy outputs appear due to instance dependent constructive interference. As illustrated in Figure 3 , these instance dependent heavy outputs pushes the probability of sampling the optimum from the design baseline into the finite probability regime. Additional contributions from parameter optimization are discussed in Sec. 4.3.
Polytime Hybrid Quantum–Classical Solver (PHQC)
We now extend the algorithmic pipeline to include a coarse grid search over ( γ , β ) (\gamma,\beta) ( γ , β ) parameters as used in § 3.1 and an exact classical checker that returns the lowest energy feasible bitstring regardless of its empirical frequency. Let β ∈ [ 0 , π ] \beta\in[0,\pi] β ∈ [ 0 , π ] , γ ∈ [ 0 , π ] \gamma\in[0,\pi] γ ∈ [ 0 , π ] . For a chosen depth p p p , we build a rectangular grid
G = { ( β i , γ j ) : β i = i Δ β , γ j = j Δ γ , 0 ≤ i ≤ N β , 0 ≤ j ≤ N γ } , \mathcal{G}=\{(\beta_i,\gamma_j):\ \beta_i=i\,\Delta_\beta,\ \gamma_j=j\,\Delta_\gamma,\ 0\le i\le N_\beta,\ 0\le j\le N_\gamma\}, G = {( β i , γ j ) : β i = i Δ β , γ j = j Δ γ , 0 ≤ i ≤ N β , 0 ≤ j ≤ N γ } ,
with spacings Δ β , Δ γ ∈ [ 0 , π ] n + 1 \Delta_\beta,\Delta_\gamma\in[0,\pi]^{n+1} Δ β , Δ γ ∈ [ 0 , π ] n + 1 as in Theorem 13 . Given a multiset of measured bitstrings S S S , the checker evaluates exact objective values E ( b ) = ⟨ b ∣ H o b j ∣ b ⟩ E(b)=\langle b|H_{\mathrm{obj}}|b\rangle E ( b ) = ⟨ b ∣ H obj ∣ b ⟩ for all b ∈ S b\in S b ∈ S and returns the minimal element. Consequently, it is irrelevant whether the optimal bitstring is the most frequent sample. Any single appearance of an optimal b ⋆ b^\star b ⋆ suffices for the checker to output the optimum. This strengthens the overall protocol and minimizes the shot budget. The deterministic post-processing performs scoring b ↦ ⟨ b ∣ H C ∣ b ⟩ b\mapsto\langle b|H_C|b\rangle b ↦ ⟨ b ∣ H C ∣ b ⟩ in O ( n 2 ) O(n^2) O ( n 2 ) with total classical work O ( S n 2 ) O(Sn^2) O ( S n 2 ) .
Lemma 24 (Chernoff bound for optimum hits). Let N ⋆ N_\star N ⋆ be the number of optimal bitstrings observed in S S S independent samples, each occurring with probability p min ( ϵ ) p_{\min}(\epsilon) p m i n ( ϵ ) . Then
Pr [ N ⋆ = 0 ] ≤ exp ( − p min ( ϵ ) S ) , S ≥ ⌈ ln ( 1 / δ ) p min ( ϵ ) ⌉ ⟹ Pr [ N ⋆ ≥ 1 ] ≥ 1 − δ . \Pr[N_\star=0]\le\exp(-p_{\min}(\epsilon)S),\qquad S\ge\left\lceil\frac{\ln(1/\delta)}{p_{\min}(\epsilon)}\right\rceil\Longrightarrow\Pr[N_\star\ge1]\ge1-\delta. Pr [ N ⋆ = 0 ] ≤ exp ( − p m i n ( ϵ ) S ) , S ≥ ⌈ p m i n ( ϵ ) ln ( 1/ δ ) ⌉ ⟹ Pr [ N ⋆ ≥ 1 ] ≥ 1 − δ .
Proof. Let X i ∼ Bernoulli ( p min ( ϵ ) ) X_i \sim\operatorname{Bernoulli}(p_{\min}(\epsilon)) X i ∼ Bernoulli ( p m i n ( ϵ )) be the indicator for an optimum hit in shot i i i . Then N ⋆ = ∑ i = 1 S X i N_{\star} = \sum_{i=1}^{S} X_i N ⋆ = ∑ i = 1 S X i with E [ N ⋆ ] = S p min ( ϵ ) \mathbb{E}[N_{\star}] = S p_{\min}(\epsilon) E [ N ⋆ ] = S p m i n ( ϵ ) . Using Pr [ N ⋆ = 0 ] = ( 1 − p min ) S ≤ e − p min S \Pr[N_{\star}=0] = (1-p_{\min})^{S} \le e^{-p_{\min}S} Pr [ N ⋆ = 0 ] = ( 1 − p m i n ) S ≤ e − p m i n S proves the first inequality; the shot bound follows by inversion.
Theorem 25 (Sample complexity for perfect recovery). Let p min > 0 p_{\min}>0 p m i n > 0 be the total probability mass on the optimal bit-strings after p p p Constraint-Enhanced QAOA layers. With S ≥ ⌈ ln ( δ − 1 ) / p min ⌉ S \ge\lceil\ln(\delta^{-1})/p_{\min} \rceil S ≥ ⌈ ln ( δ − 1 ) / p m i n ⌉ shots, the PHQC post-processor returns a globally optimal solution with probability at least 1 − δ 1-\delta 1 − δ .
Sketch. Apply Lemma 24 with p min ( ϵ ) = p min p_{\min}(\epsilon)=p_{\min} p m i n ( ϵ ) = p m i n .
Algorithm 4 PHQC — constant-depth CE–QAOA + deterministic checker
Require: size n n n ; depth p p p ; grid G \mathcal{G} G over ( β , γ ) (\beta,\gamma) ( β , γ ) ; H C = H p e n + H o b j H_C=H_{\mathrm{pen}}+H_{\mathrm{obj}} H C = H pen + H obj ; mixer H M H_M H M ; shots S = ⌈ n k ln ( 1 / δ ) ⌉ S=\lceil n^k\ln(1/\delta)\rceil S = ⌈ n k ln ( 1/ δ )⌉ .
Ensure: optimal feasible ( b ⋆ , c ⋆ ) (b^\star,c^\star) ( b ⋆ , c ⋆ ) .
∣ s 0 ⟩ ← ∣ s b l k ⟩ ⊗ m |s_0\rangle\leftarrow|s_{\mathrm{blk}}\rangle^{\otimes m} ∣ s 0 ⟩ ← ∣ s blk ⟩ ⊗ m .
S ← ∅ \mathcal{S} \leftarrow\varnothing S ← ∅ .
for each ( β , γ ) ∈ G (\beta,\gamma)\in\mathcal{G} ( β , γ ) ∈ G do
prepare ∣ s 0 ⟩ |s_0\rangle ∣ s 0 ⟩ ; apply U C ( γ ) U_C(\gamma) U C ( γ ) ; apply U M ( β ) U_M(\beta) U M ( β ) ; measure S S S shots into S \mathcal{S} S .
end for
( b ⋆ , c ⋆ ) ← ( n u l l , + ∞ ) (b^\star,c^\star)\leftarrow(\mathrm{null},+\infty) ( b ⋆ , c ⋆ ) ← ( null , + ∞ ) .
for each b ∈ S b\in\mathcal{S} b ∈ S do
if Feasible ( b ) \operatorname{Feasible}(b) Feasible ( b ) then
c ← ⟨ b ∣ H o b j ∣ b ⟩ c\leftarrow\langle b|H_{\mathrm{obj}}|b\rangle c ← ⟨ b ∣ H obj ∣ b ⟩ ▷ or full H C H_C H C if you score penalties
if c < c ⋆ c<c^\star c < c ⋆ then
( b ⋆ , c ⋆ ) ← ( b , c ) (b^\star,c^\star)\leftarrow(b,c) ( b ⋆ , c ⋆ ) ← ( b , c )
end if
end if
end for
return ( b ⋆ , c ⋆ ) (b^\star,c^\star) ( b ⋆ , c ⋆ ) .
Circuit Simulation Results
Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is defined on a complete weighted graph G = ( V , E ) G=(V,E) G = ( V , E ) , ∣ V ∣ = n |V|=n ∣ V ∣ = n , with distance matrix C a b ∈ R ≥ 0 n × n C_{ab}\in\mathbb{R}_{\ge0}^{n\times n} C ab ∈ R ≥ 0 n × n . A tour is a Hamiltonian cycle visiting each city exactly once. We represent a tour by an n × n n\times n n × n binary assignment matrix X = ( x i , a ) X=(x_{i,a}) X = ( x i , a ) where row i i i indicates the city visited at position i i i in the tour and column a a a indicates which city. Each position is assigned exactly one city and each city appears exactly once,
∑ a = 1 n x i , a = 1 ( ∀ i ) , ∑ i = 1 n x i , a = 1 ( ∀ a ) , x i , a ∈ { 0 , 1 } . (11) \sum_{a=1}^{n}x_{i,a}=1\quad(\forall i),\qquad\sum_{i=1}^{n}x_{i,a}=1\quad(\forall a),\qquad x_{i,a}\in\{0,1\}. \tag*{(11)} a = 1 ∑ n x i , a = 1 ( ∀ i ) , i = 1 ∑ n x i , a = 1 ( ∀ a ) , x i , a ∈ { 0 , 1 } . (11)
This is the double one-hot encoding. It matches our block structure defined in Def. 1 with each of the m = n m=n m = n rows defined as a one-hot block of size n n n .
On the computational basis x ↦ X = ( x i , a ) x\mapsto X=(x_{i,a}) x ↦ X = ( x i , a ) 6 and the objective is the cyclic pairwise cost between consecutive positions:
H o b j ( x ) = ∑ i = 1 n ∑ a , b = 1 n C a b x i , a x i + 1 , b ( i + 1 ≡ 1 ) . (12) H_{\mathrm{obj}}(x)=\sum_{i=1}^{n}\sum_{a,b=1}^{n}C_{ab}x_{i,a}x_{i+1,b}\qquad(i+1\equiv1). \tag*{(12)} H obj ( x ) = i = 1 ∑ n a , b = 1 ∑ n C ab x i , a x i + 1 , b ( i + 1 ≡ 1 ) . (12)
Feasibility is enforced by quadratic penalties for row/column sums,
H p e n ( x ) = λ r o w ∑ i = 1 n ( ∑ a = 1 n x i , a − 1 ) 2 + λ c o l ∑ a = 1 n ( ∑ i = 1 n x i , a − 1 ) 2 , (13) H_{\mathrm{pen}}(x)=\lambda_{\mathrm{row}}\sum_{i=1}^{n}\left(\sum_{a=1}^{n}x_{i,a}-1\right)^{2}+\lambda_{\mathrm{col}}\sum_{a=1}^{n}\left(\sum_{i=1}^{n}x_{i,a}-1\right)^{2}, \tag*{(13)} H pen ( x ) = λ row i = 1 ∑ n ( a = 1 ∑ n x i , a − 1 ) 2 + λ col a = 1 ∑ n ( i = 1 ∑ n x i , a − 1 ) 2 , (13)
optionally augmented by linear forbids (e.g., disallowing self-loops or precluded edges). The double one-hot constraints enforce a permutation of the visited locations. The first term in Eq (13) is now redundant and can be dropped. The cost Hamiltonian is H C = H p e n + H o b j H_C=H_{\mathrm{pen}}+H_{\mathrm{obj}} H C = H pen + H obj , which is diagonal in the computational basis and fits our kernel requirements in Def 1. See [24 ] for detailed QUBO derivations and discussions.
Numerical validation on approximate circuit simulators
We benchmark the CE-QAOA on QOPTLib instances[30 ] by setting a fixed start city (“anchored” reduction), which yields ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 logical qubits (blocks = n − 1 =n-1 = n − 1 , block size = n − 1 =n-1 = n − 1 ) for a problem defined on n n n locations. We work with a single layer composed as U ( γ , β ) = U M ( β ) U C ( γ ) U(\gamma,\beta)=U_M(\beta)U_C(\gamma) U ( γ , β ) = U M ( β ) U C ( γ ) . We sweep a grid G ⊂ [ 0 , π ] 2 \mathcal{G}\subset[0,\pi]^2 G ⊂ [ 0 , π ] 2 with ∣ G ∣ = ( n + 1 ) 2 |\mathcal{G}|=(n+1)^2 ∣ G ∣ = ( n + 1 ) 2 angle pairs, and use a shot budget of S = 10 n k S=10n^k S = 10 n k with k k k ranging from 3–5 which comfortably absorbs finite-precision and rounding effects of the grid search and finite sampling since the number of qubits scales as O ( n 2 ) O(n^2) O ( n 2 ) . For each grid point we measure in the computational basis, classically filter feasible solutions, and evaluate cyclic tour costs relative to the fixed start. We report (i) the best measured feasible solution, (ii) the fraction of feasible outcomes, and (iii) the minimum tour cost. In Table 1 , the PHQC recovered the optimum in all cases. The fact that Algorithm 4 guarantees any sampled optimal bitstring to be identified regardless of its frequency, greatly reduces the shot burden in our implementation.7
reshape x ↦ X x\mapsto X x ↦ X merely clarifies the row/column one-hot constraints and the cyclic pairwise objective H o b j ( x ) = ∑ i , a , b C a b x i , a x i + 1 , b H_{\mathrm{obj}}(x)=\sum_{i,a,b}C_{ab}x_{i,a}x_{i+1,b} H obj ( x ) = ∑ i , a , b C ab x i , a x i + 1 , b , which naturally refer to this matrix structure.
Classical Competitiveness II: Theta(n r n^r n r ) Sampling Advantage
The ε \varepsilon ε -approximate 2-design on the encoded manifold gives Haar-like second-moment anticoncentration at scale 1 / D 1/D 1/ D with D = n m D = n^m D = n m (Thm. 20), which is a conservative worst-case sampling floor and a predictor of typical-case overlap statistics (Cor. 21). However, there are two empirical observations to be made at depth p = 1 p=1 p = 1 . (i) Polynomial-shot recovery across instances with a basic coarse grid search over the ( γ , β ) (\gamma,\beta) ( γ , β ) parameter space. (ii) Systematic peaks above 1 / D 1/D 1/ D when the block-permutation twirl is omitted (Figure 4 ) suggesting that the native labeling preserves instance structure and constructive interference. This is expected to remain the case at higher layers with p > 1 p > 1 p > 1 . These empirical observations therefore motivate a targeted search over angle pairs and shallow depths to find constructive-interference settings that achieve per-shot success at the heuristic scale
p min ≳ 1 n k for k < m . (14) p_{\min} \gtrsim\frac{1}{n^k}\quad\text{for } k<m. \tag*{(14)} p m i n ≳ n k 1 for k < m . (14)
To see how this might arise under finer angle and layer optimization, we can think of each fixed block in m m m as systematically reducing the effective degrees of freedom from m m m blocks down to k k k . We start in a uniform superposition of block one-hot basis vectors and assume that at least one block can be fixed at the beginning of the optimization process. This is no different from fixing the starting position in the TSP. The parameter optimization process fixes further block(s) to minimize the objective function. Thanks to the global constraint, each layer can be further assumed to slightly favor configurations that agree with a target pattern on a few blocks with a suitable angle choice. These blocks are then assumed locked . Meaning that finer parameter optimization at current layer or next can yield a new set of parameters that improves the number of locks but not degrade it. We can think of a block as locked once the target symbol in that block gains a fixed margin over the uniform 1 / n 1/n 1/ n baseline and k k k is interpreted as residual “undecided” blocks. Because of the global constraint, subsequent layers leverage already-locked blocks to bias additional ones, producing a cascade that leaves only k k k blocks unfixed.
At that point the success probability depends only on these k k k degrees of freedom and is therefore bounded below by 1 / n k 1/n^k 1/ n k independent of the ambient dimension D = n m D = n^m D = n m . The success probability in Eq. (14) follows. PHQC then converts this into polynomial shot complexity, S ≥ ⌈ log ( 1 / δ ) / p min ⌉ = O ( n k log ( 1 / δ ) ) S \ge\lceil\log(1/\delta)/p_{\min}\rceil= O(n^k\log(1/\delta)) S ≥ ⌈ log ( 1/ δ ) / p m i n ⌉ = O ( n k log ( 1/ δ )) (Thm. 25). With the classical shot cost given as S c l = Θ ( n m − 1 log ( 1 / δ ) ) S_{\mathrm{cl}} = \Theta(n^{m-1}\log(1/\delta)) S cl = Θ ( n m − 1 log ( 1/ δ )) shots, the ratio is
S c l S q = Θ ( n r ) , (15) \frac{S_{\mathrm{cl}}}{S_{\mathrm{q}}} = \Theta(n^r), \tag*{(15)} S q S cl = Θ ( n r ) , (15)
Where r = m − 1 − k r = m - 1 - k r = m − 1 − k . Taking into account the clear upward trend in Table 1 ; with r = 6 r = 6 r = 6 for n = 15 n = 15 n = 15 problem, the quantitative advantage exceeds 10 7 10^7 1 0 7 . It goes without saying that better circuit approximations would improve accuracy and amplify the advantage.
Near-Optimality of Grid Parameters
It is also worth noting that our coarse parameter grid is far from optimal. We use it here as a sufficient condition for the existence of parameters that can yield the design based
and uniformly from feasible bitstrings, the success probability for a unique optimum is
p s u c c = 1 n ! ⇒ S c l = Θ ( n ! log ( 1 / δ ) ) . p_{\mathrm{succ}} = \frac{1}{n!} \quad\Rightarrow\quad S_{\mathrm{cl}} = \Theta(n!\log(1/\delta)). p succ = n ! 1 ⇒ S cl = Θ ( n ! log ( 1/ δ )) .
Given the rapid growth of n ! n! n ! , the advantage persists, with tweaks in prefactors and orders of magnitude. results and subsequent large reduction in shot cost expected when the twirling averaging is bypassed. The approximate 2-design results suggest inherent trainability and anticoncentration in the proposed construction. Empirically, increasing the grid points yields more frequent near-optimal interference within the same shot budget. For example, at n = 8 n = 8 n = 8 , using 20 × 20 20 \times20 20 × 20 grids for ( γ , β ) (\gamma,\beta) ( γ , β ) (instead of ( n + 1 ) × ( n + 1 ) = 9 × 9 (n+1) \times(n+1) = 9 \times9 ( n + 1 ) × ( n + 1 ) = 9 × 9 ) and the same shot budget of 10 n 3 = 5120 10n^3 = 5120 10 n 3 = 5120 produced 12 angle pairs attaining the optimum, and 40 angle pairs within 1% of the optimum and 229 points within 5% of the optimum. Whereas the coarser grid of size n + 1 n+1 n + 1 found only 2 pairs of grid points attaining the optimum. Similar phenomenon was observed for problems with n = 9 n = 9 n = 9 and 10 respectively. This supports our choice to prioritize density over range and treat [ 0 , π ] 2 [0,\pi]^2 [ 0 , π ] 2 as a sufficient compact tile for practical scans, while leaving systematic parameter optimization for future work.
Approximate circuit simulation as probes. All circuit evaluations are performed using a matrix-product-state (MPS) simulator in the sense of Vidal’s tensor-network formulation [56 ] . Specifically, we used the matrix_product_state backend of the IBM Qiskit Aer simulator [52 ] . For reproducibility, we configured the backend in a deliberately aggressive truncation regime with maximum bond dimension of 128, truncation and validation thresholds of 10 − 3 10^{-3} 1 0 − 3 , and an amplitude-chopping threshold of 10 − 3 10^{-3} 1 0 − 3 . Even under these approximations, the CE–QAOA circuit consistently recovers optimal tours on instances of size 4 to 10 nodes. This strongly suggests that the diagonal entangler (Prop. 19 ) and constant-gap block–XY mixer (Prop. 7) induce useful interference patterns already at modest entanglement, aligning with the encoded 2-design baseline (Thm. 20 ) as a conservative control. Because truncation damps constructive interference, we expect the non-twirled peaks to sharpen under higher-fidelity simulation, increasing the single-shot success p min p_{\min} p m i n and directly reducing the required shots at fixed confidence. Larger instances (15–25 nodes) were probed only at zero angles due to the prohibitive wall-time for full MPS simulation on commodity hardware.
The truncations we employ motivate near-term hardware probes on devices that admit the circuit width/depth of these instances or their compressed variants. Our grid over ( γ , β ) (\gamma,\beta) ( γ , β ) , define a calibration surface for algorithm–hardware co-design . Compilers can target mixer locality; error-mitigation can prioritize preserving diagonal-phase coherence; and hardware can be tuned to maintain the short-depth interference that creates the observed peaks. The encoded 2-design baseline (Thm. 20 ) supplies a Haar-like null model at scale 1 / D 1/D 1/ D against which hardware-induced deviations can be quantitatively assessed. We therefore propose our CE-QAOA kernel with Table 1 as references for probing future hardwares.
PHQC vs. classical exact/heuristic solvers. High-quality heuristics (like LKH implementation) routinely find near-optimal tours quickly [6 ] , and exact methods (e.g., branch-and-cut as in Concorde) provide provably optimal solutions in practice on large benchmarks [57 ] . Dynamic programming à la Bellman–Held–Karp offers a systematic exact approach with worst-case complexity T H K = Θ ( n 2 2 n ) T_{\mathrm{HK}} = \Theta(n^2 2^n) T HK = Θ ( n 2 2 n ) time and M H K = Θ ( n 2 n ) M_{\mathrm{HK}} = \Theta(n2^n) M HK = Θ ( n 2 n ) memory [58 ] . By contrast, our PHQC protocol gives a probabilistic recovery guarantee where a per-shot optimal-hit probability p min p_{\min} p m i n at selected shallow angles, S ≥ ⌈ ln ( 1 / δ ) / p min ⌉ S \ge\lceil\ln(1/\delta)/p_{\min} \rceil S ≥ ⌈ ln ( 1/ δ ) / p m i n ⌉ shots suffice to obtain the optimal tour with probability at least 1 − δ 1-\delta 1 − δ (Thm. 25 ). This is incomparable to the worst-case exponential bound of dynamic programming. While PHQC provides randomized anytime certificates (via repeats to boost 1 − δ 1-\delta 1 − δ ), DP provides deterministic exactness with exponential resources. We leave a rigorous head-to-head comparison between exact solvers and PHQC to future work. However, we collect the first indication of the ability of the instance dependent heavy outputs to keep the per-shot success probability in the finite shot region in the Table 2 and Figure 5 .
Figure 5. Heavy outputs vs. finite-shot thresholds. Shaded green shows the finite-shot region p ≥ 1 10 n 3 p \ge\frac{1}{10n^3} p ≥ 10 n 3 1 . Theorem-level guarantees (yellow boundary in schematic figures) place us above this curve, while instance-dependent heavy outputs (blue points/curve) push into the finite-shot regime Cf. 3.
Table 2. Empirical verification of polynomial single-shot success probability from non-twirled circuit outputs. k k k is the degeneracy observed in the sampled bitstrings while n r e d n_{\mathrm{red}} n red is teh number of blocks left after fixing the starting position. The twirling baseline = 1 / D = 1/D = 1/ D . The choice of ln ( 1 / δ ) = 10 \ln(1/\delta) = 10 ln ( 1/ δ ) = 10 corresponds to δ = e − 10 ≈ 4.5 × 10 − 5 \delta= e^{-10} \approx4.5 \times10^{-5} δ = e − 10 ≈ 4.5 × 1 0 − 5 , a very stringent failure probability (≈ 0.005 % \approx0.005\% ≈ 0.005% ). p o p t p_{\mathrm{opt}} p opt sums probabilities over all degenerate optimal bitstrings.
Conclusion
We introduced CE–QAOA, a constraint–aware kernel that (i) prepares and preserves a block one–hot manifold with an ancilla–free, depth–optimal encoder and a constant–gap two–local block–XY mixer; (ii) establishes low–order unitary moments—an exact 1–design via block–permutation twirling and an approximate 2–design from short per–block XY evolutions combined with a diagonal inter–block entangler; (iii) yields a Paley–Zygmund anticoncentration and typical–case overlap guarantees at the 1 / D 1/D 1/ D scale for encoded dimension D = n m D = n^m D = n m ; (iv) couples naturally to a deterministic classical post–processor (PHQC) that converts overlap into an end–to–end solver with explicit shot complexity; and (v) frames a quantum–classical separation based on access models that make explicit what the classical sampler can generate efficiently. Algorithmically, PHQC identifies the best feasible sample in O ( S n 2 ) O(Sn^2) O ( S n 2 ) classical time. This implies that obtaining a shot complexity independent of the encoded dimension D D D is the path to an unconditional quantum advantage with a polynomial time quantum–classical solver. We show empirically that in absence of permutation twirling, instance dependent interference leads to heavy outputs in the probability profile far above the design baseline into the polynomial shot regime.
We subsequently develop an inductive explanation to suggest that this arises in CE–QAOA when only a fraction of blocks remain unaligned on the target solution during parameter optimization. Our observation suggests that when CE–QAOA is seeded with a fixed starting block, it concentrates weight so that success depends on the number k k k of unaligned blocks at the end of state preparation. Typically k ≪ m k \ll m k ≪ m , and the effective scale shifts from 1 / n m 1/n^{m} 1/ n m to about 1 / n k 1/n^{k} 1/ n k , yielding orders-of-magnitude gains. Thus, we obtain a Θ ( n r ) \Theta(n^{r}) Θ ( n r ) shot-complexity advantage whenever CE–QAOA locks r ≥ 1 r \ge1 r ≥ 1 blocks. This advantage would persist even if a classical sampler drew uniformly from the feasible space itself because classical sampling offers no mechanism to overcome the exponential suppression of success probability. We leave a rigorous proof of this phenomenon to future work.
However, when a classical competitor only samples raw N = n 2 N = n^{2} N = n 2 bitstrings and relies on a feasibility predicate, while CE–QAOA prepares states directly in H O H \mathcal{H}_{\mathrm{OH}} H OH , the expected trial counts differ by an exp [ Θ ( n 2 ) ] \exp[\Theta(n^{2})] exp [ Θ ( n 2 )] factor in a minimax sense. We view these results as a step toward symmetry-inspired, shallow quantum heuristics with analyzable typical-case behavior and clean interfaces to efficient classical checking. Finally, our paper illustrates the practical impact of encoded designs in optimization problems. We observe that due to the typical behaviour results that emerge from this method, the bounds always tend to be conservative. We hope that future works are able to go beyond unitary designs to prove a worst case shot complexity independent of the encoded dimension D D D , paving the way for unconditional quantum advantage.
CE-QAOA Circuit Diagrams and Block-Constraint Example
In a typical QAOA formulation with N N N qubits, the full Hilbert space is H ⊗ N \mathcal{H}^{\otimes N} H ⊗ N with dimension 2 N 2^N 2 N .
For the case where N = n 2 N=n^2 N = n 2 (i.e., n 2 n^2 n 2 qubits), the full space has dimension
dim ( H f u l l ) = 2 n 2 . \dim(\mathcal{H}_{\mathrm{full}})=2^{n^2}. dim ( H full ) = 2 n 2 .
Suppose we partition the n 2 n^2 n 2 qubits into n n n blocks of n n n qubits each. We require that each block is restricted to states of the form
∣ 0 ⋯ 1 i ⋯ 0 ⟩ , i = 0 , … , n − 1. \lvert0\cdots1_i\cdots0\rangle,\qquad i=0,\ldots,n-1. ∣ 0 ⋯ 1 i ⋯ 0 ⟩ , i = 0 , … , n − 1.
The projector onto the one-hot subspace for block j j j is defined as
P n ( j ) = ∑ i = 0 n − 1 ∣ 0 ⋯ 1 i ⋯ 0 ⟩ j ⟨ 0 ⋯ 1 i ⋯ 0 ∣ j . P_n^{(j)}=\sum_{i=0}^{n-1}\lvert0\cdots1_i\cdots0\rangle_j\langle0\cdots1_i\cdots0\rvert_j. P n ( j ) = i = 0 ∑ n − 1 ∣ 0 ⋯ 1 i ⋯ 0 ⟩ j ⟨ 0 ⋯ 1 i ⋯ 0 ∣ j .
The overall projector on the full system is then
P = ⨂ j = 0 n − 1 P n ( j ) . P=\bigotimes_{j=0}^{n-1}P_n^{(j)}. P = j = 0 ⨂ n − 1 P n ( j ) .
which restricts the Hilbert space to the tensor product of one-hot subspaces. Since each block now has dimension n n n , the dimension of the one-hot subspace is
dim ( H o n e − h o t ) = n n . \dim(\mathcal{H}_{\mathrm{one-hot}})=n^n. dim ( H one − hot ) = n n .
Here we illustrate the Kernel structure of Definition 1 for the Traveling Salesman Problem [24 ] . Suppose we have a 3-city TSP-like problem requiring a 3 × 3 3\times3 3 × 3 binary matrix encoding. In the block-wise viewpoint we need 9 qubits grouped into 3 blocks, representing the rows of the permutation matrix (each block represents which city is in the 1 1 1 st, 2 2 2 nd, or 3 3 3 rd position). Each block has 3 qubits (exactly one of the 3 qubits is ∣ 1 ⟩ \lvert1\rangle ∣ 1 ⟩ , the others ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ ). A valid bitstring in the computational basis then takes the form
( b 0 0 b 0 1 b 0 2 ) ∣ ( b 1 0 b 1 1 b 1 2 ) ∣ ( b 2 0 b 2 1 b 2 2 ) , (b_0^0 b_0^1 b_0^2)\mid(b_1^0 b_1^1 b_1^2)\mid(b_2^0 b_2^1 b_2^2), ( b 0 0 b 0 1 b 0 2 ) ∣ ( b 1 0 b 1 1 b 1 2 ) ∣ ( b 2 0 b 2 1 b 2 2 ) ,
where each parenthetical group has exactly one ∣ 1 ⟩ \lvert1\rangle ∣ 1 ⟩ . For example:
100 ⏟ Block 0 010 ⏟ Block 1 001 ⏟ Block 2 , \underbrace{100}_{\text{Block 0}}\ \underbrace{010}_{\text{Block 1}}\ \underbrace{001}_{\text{Block 2}}, Block 0 100 Block 1 010 Block 2 001 ,
010 ⏟ Block 0 100 ⏟ Block 1 001 ⏟ Block 2 , \underbrace{010}_{\text{Block 0}}\ \underbrace{100}_{\text{Block 1}}\ \underbrace{001}_{\text{Block 2}}, Block 0 010 Block 1 100 Block 2 001 ,
001 ⏟ Block 0 100 ⏟ Block 1 010 ⏟ Block 2 , \underbrace{001}_{\text{Block 0}}\ \underbrace{100}_{\text{Block 1}}\ \underbrace{010}_{\text{Block 2}}, Block 0 001 Block 1 100 Block 2 010 ,
etc. Each triple of bits has exactly one ∣ 1 ⟩ \lvert1\rangle ∣ 1 ⟩ and so on.
Suppose we have a 4-city TSP-like problem requiring a 4 × 4 4\times4 4 × 4 binary matrix encoding. The block structure in the computational basis then takes the form
( b 0 0 b 0 1 b 0 2 b 0 3 ) ∣ ( b 1 0 b 1 1 b 1 2 b 1 3 ) ∣ ( b 2 0 b 2 1 b 2 2 b 2 3 ) ∣ ( b 3 0 b 3 1 b 3 2 b 3 3 ) , (b_0^0 b_0^1 b_0^2 b_0^3)\mid(b_1^0 b_1^1 b_1^2 b_1^3)\mid(b_2^0 b_2^1 b_2^2 b_2^3)\mid(b_3^0 b_3^1 b_3^2 b_3^3), ( b 0 0 b 0 1 b 0 2 b 0 3 ) ∣ ( b 1 0 b 1 1 b 1 2 b 1 3 ) ∣ ( b 2 0 b 2 1 b 2 2 b 2 3 ) ∣ ( b 3 0 b 3 1 b 3 2 b 3 3 ) ,
where each parenthetical group has exactly one ∣ 1 ⟩ \lvert1\rangle ∣ 1 ⟩ . It is worth emphasizing again that not all the bitstrings satisfying this blockwise constraint are valid tours, however, all valid tours satisfy this structure. So for a TSP, the constraint is only partially encoded.
Permutation Group Actions
Global feasibility–preserving action. Let A ≡ S m × S n ⊂ U ( H O H ) \mathcal{A}\equiv S_m\times S_n\subset U(\mathcal{H}_{\mathrm{OH}}) A ≡ S m × S n ⊂ U ( H OH ) , act by
P σ , τ ( ∣ e j 0 ⟩ ⊗ ⋯ ⊗ ∣ e j m − 1 ⟩ ) = ∣ e τ ( j σ − 1 ( 0 ) ) ⟩ ⊗ ⋯ ⊗ ∣ e τ ( j σ − 1 ( m − 1 ) ) ⟩ (16) P_{\sigma,\tau}\left(\lvert e_{j_0}\rangle\otimes\cdots\otimes\lvert e_{j_{m-1}}\rangle\right)
=
\lvert e_{\tau(j_{\sigma^{-1}(0)})}\rangle\otimes\cdots\otimes\lvert e_{\tau(j_{\sigma^{-1}(m-1)})}\rangle \tag*{(16)} P σ , τ ( ∣ e j 0 ⟩ ⊗ ⋯ ⊗ ∣ e j m − 1 ⟩ ) = ∣ e τ ( j σ − 1 ( 0 ) ) ⟩ ⊗ ⋯ ⊗ ∣ e τ ( j σ − 1 ( m − 1 ) ) ⟩ (16)
i.e., a row permutation σ ∈ S m \sigma\in S_m σ ∈ S m and the same column relabeling τ ∈ S n \tau\in S_n τ ∈ S n applied to every block. When H p e n H_{\mathrm{pen}} H pen is S m × S n S_m \times S_n S m × S n –invariant (Def. 1 ), the feasible set
X : = L 0 ( H p e n ) = { x : ⟨ x ∣ H p e n ∣ x ⟩ = 0 } \mathcal{X} := L_0(H_{\mathrm{pen}}) = \{x : \langle x|H_{\mathrm{pen}}|x\rangle= 0\} X := L 0 ( H pen ) = { x : ⟨ x ∣ H pen ∣ x ⟩ = 0 }
is preserved setwise by A \mathcal{A} A .
Block Level feasibility–preserving action.
Let
B ≡ S n × m = { P = ⨂ b = 0 m − 1 P b : P b ∈ S n } ⊂ U ( H O H ) , \mathcal{B} \equiv S_n^{\times m} = \left\{P = \bigotimes_{b=0}^{m-1} P_b : P_b \in S_n\right\} \subset U(\mathcal{H}_{\mathrm{OH}}), B ≡ S n × m = { P = b = 0 ⨂ m − 1 P b : P b ∈ S n } ⊂ U ( H OH ) ,
which applies independent label permutations in each block. This action is not feasibility–preserving in general (it can break column one–hot), but it does implement a first–moment (1-design) average on the encoded space. By a permutation twirl we mean the feasibility–preserving group action
A = S m ( r o w s ) × S n ( g l o b a l c o l s ) , \mathcal{A} = S_m^{(\mathrm{rows})} \times S_n^{(\mathrm{global\ cols})}, A = S m ( rows ) × S n ( global cols ) ,
which (i) permutes the rows/blocks uniformly via a single π ∈ S m \pi\in S_m π ∈ S m and (ii) applies the same column relabeling τ ∈ S n \tau\in S_n τ ∈ S n to every row. This action preserves the set of permutation matrices (feasible states).
Recall. If we encode an m × n m \times n m × n assignment (rows b ∈ [ m ] b \in[m] b ∈ [ m ] , columns j ∈ [ n ] j \in[n] j ∈ [ n ] ) by an m m m -block one–hot pattern with n n n qubits per block. A feasible bitstring is a permutation matrix X ∈ { 0 , 1 } m × n X \in\{0,1\}^{m \times n} X ∈ { 0 , 1 } m × n with exactly one “1” in each row and each column. Let S m S_m S m act on rows (blocks) and S n S_n S n act on columns (symbols) with action on X X X given by
( R π X ) b , j = X π − 1 ( b ) , j , π ∈ S m , (17) (R_\pi X)_{b,j} = X_{\pi^{-1}(b),j}, \qquad\pi\in S_m, \tag*{(17)} ( R π X ) b , j = X π − 1 ( b ) , j , π ∈ S m , (17)
( C τ X ) b , j = X b , τ − 1 ( j ) , τ ∈ S n , (18) (C_\tau X)_{b,j} = X_{b,\tau^{-1}(j)}, \qquad\tau\in S_n, \tag*{(18)} ( C τ X ) b , j = X b , τ − 1 ( j ) , τ ∈ S n , (18)
and combined action X ↦ R π C τ X X \mapsto R_\pi C_\tau X X ↦ R π C τ X .
Proposition 26 (Global Feasibility is preserved by A \mathcal{A} A ). If X X X is a permutation matrix and ( π , τ ) ∈ A (\pi,\tau) \in\mathcal{A} ( π , τ ) ∈ A , then X ′ : = R π C τ X X' := R_\pi C_\tau X X ′ := R π C τ X is also a permutation matrix .
Proof. Any feasible X X X encodes a permutation σ : [ m ] → [ n ] \sigma: [m] \to[n] σ : [ m ] → [ n ] via X b , j = 1 ⟺ j = σ ( b ) X_{b,j} = 1 \Longleftrightarrow j = \sigma(b) X b , j = 1 ⟺ j = σ ( b ) . Under the group action,
( R π C τ X ) b , j = 1 ⟺ X π − 1 ( b ) , τ − 1 ( j ) = 1 ⟺ τ − 1 ( j ) = σ ( π − 1 ( b ) ) ⟺ j = τ ( σ ( π − 1 ( b ) ) ) (R_\pi C_\tau X)_{b,j} = 1 \Longleftrightarrow X_{\pi^{-1}(b),\tau^{-1}(j)} = 1 \Longleftrightarrow\tau^{-1}(j) = \sigma(\pi^{-1}(b)) \Longleftrightarrow j = \tau(\sigma(\pi^{-1}(b))) ( R π C τ X ) b , j = 1 ⟺ X π − 1 ( b ) , τ − 1 ( j ) = 1 ⟺ τ − 1 ( j ) = σ ( π − 1 ( b )) ⟺ j = τ ( σ ( π − 1 ( b ))) .
Thus R π C τ X R_\pi C_\tau X R π C τ X encodes the permutation τ ∘ σ ∘ π − 1 \tau\circ\sigma\circ\pi^{-1} τ ∘ σ ∘ π − 1 . It remains one-hot in each row and each column, i.e. feasible. □
For a qubit-level description, label qubits as ( b , j ) (b,j) ( b , j ) with b ∈ [ m ] b \in[m] b ∈ [ m ] (block/row) and j ∈ [ n ] j \in[n] j ∈ [ n ] (column). Then
( b , j ) ↦ R π ( π ( b ) , j ) , (19) (b,j) \xmapsto{R_\pi} (\pi(b),j), \tag*{(19)} ( b , j ) R π ( π ( b ) , j ) , (19)
( b , j ) ↦ C τ ( b , τ ( j ) ) , (20) (b,j) \xmapsto{C_\tau} (b,\tau(j)), \tag*{(20)} ( b , j ) C τ ( b , τ ( j )) , (20)
and the unitary implementing R π C τ R_\pi C_\tau R π C τ is a permutation matrix over the full computational basis. Because H p e n H_{\mathrm{pen}} H pen is invariant under A \mathcal{A} A , its zero-level set is stable under these unitaries. This is the precise sense in which “the permutation preserves feasibility” in our kernel.
3 × 3 (9-qubit) example Take m = n = 3 m=n=3 m = n = 3 , so a feasible state is a 3 × 3 3 \times3 3 × 3 permutation matrix. Start from σ = i d \sigma= \mathrm{id} σ = id ,
X = ( 1 0 0 0 1 0 0 0 1 ) . X = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}. X = 1 0 0 0 1 0 0 0 1 .
Apply a row cycle π = ( 1 2 3 ) \pi=(1\ 2\ 3) π = ( 1 2 3 ) : R π X R_{\pi}X R π X is ( 0 1 0 0 0 1 1 0 0 ) \begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix} 0 0 1 1 0 0 0 1 0 , still feasible. Apply a global column swap τ = ( 1 3 ) \tau=(1\ 3) τ = ( 1 3 ) to all rows: C τ X = ( 0 0 1 0 1 0 1 0 0 ) C_{\tau}X=\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix} C τ X = 0 0 1 0 1 0 1 0 0 , still feasible. The combined action R π C τ X R_{\pi}C_{\tau}X R π C τ X remains a permutation matrix, encoding τ ∘ σ ∘ π − 1 \tau\circ\sigma\circ\pi^{-1} τ ∘ σ ∘ π − 1 .
A Quick Schmidt–Rank Primer
Definition 27 (Schmidt decomposition and Schmidt rank). Let ∣ ψ ⟩ ∈ H L ⊗ H R \lvert\psi\rangle\in\mathcal{H}_{L}\otimes\mathcal{H}_{R} ∣ ψ ⟩ ∈ H L ⊗ H R be a pure state. There exist orthonormal sets { ∣ u k ⟩ } k = 1 r ⊂ H L \{\lvert u_k\rangle\}_{k=1}^{r}\subset\mathcal{H}_{L} {∣ u k ⟩ } k = 1 r ⊂ H L , { ∣ v k ⟩ } k = 1 r ⊂ H R \{\lvert v_k\rangle\}_{k=1}^{r}\subset\mathcal{H}_{R} {∣ v k ⟩ } k = 1 r ⊂ H R , and strictly positive numbers λ 1 , … , λ r \lambda_1,\ldots,\lambda_r λ 1 , … , λ r such that
∣ ψ ⟩ = ∑ k = 1 r λ k ∣ u k ⟩ L ⊗ ∣ v k ⟩ R . \lvert\psi\rangle=\sum_{k=1}^{r}\lambda_k\lvert u_k\rangle_{L}\otimes\lvert v_k\rangle_{R}. ∣ ψ ⟩ = k = 1 ∑ r λ k ∣ u k ⟩ L ⊗ ∣ v k ⟩ R . The integer r r r is the Schmidt rank, denoted SR ( ∣ ψ ⟩ ) \operatorname{SR}(\lvert\psi\rangle) SR (∣ ψ ⟩) (with respect to the bipartition L ∣ R L|R L ∣ R ).
Matrix-reshaping. Fix product bases on L L L and R R R . If one reshapes the amplitude tensor of ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ into a matrix M ∈ C ( dim H L ) × ( dim H R ) M\in\mathbb{C}^{(\dim\mathcal{H}_{L})\times(\dim\mathcal{H}_{R})} M ∈ C ( d i m H L ) × ( d i m H R ) by grouping all “left” indices as rows and all “right” indices as columns, then
SR ( ∣ ψ ⟩ ) = rank ( M ) . \operatorname{SR}(\lvert\psi\rangle)=\operatorname{rank}(M). SR (∣ ψ ⟩) = rank ( M ) .
Thus, the Schmidt rank of a state equals the usual linear-algebra rank of its reshaped coefficient matrix.
Example: ∣ 0 ⟩ ⊗ n \lvert0\rangle^{\otimes n} ∣ 0 ⟩ ⊗ n has Schmidt rank 1 across any single-edge cut. For any cut { 0 , … , i − 1 } ∣ { i , … , n − 1 } \{0,\ldots,i-1\}\mid\{i,\ldots,n-1\} { 0 , … , i − 1 } ∣ { i , … , n − 1 } one has the factorization
∣ 0 ⟩ ⊗ n = ( ∣ 0 ⟩ ⊗ i ) ⊗ ( ∣ 0 ⟩ ⊗ ( n − i ) ) , \lvert0\rangle^{\otimes n}=\left(\lvert0\rangle^{\otimes i}\right)\otimes\left(\lvert0\rangle^{\otimes(n-i)}\right), ∣ 0 ⟩ ⊗ n = ( ∣ 0 ⟩ ⊗ i ) ⊗ ( ∣ 0 ⟩ ⊗ ( n − i ) ) ,
i.e. a single product term. Hence SR = 1 \operatorname{SR}=1 SR = 1 . In the matrix view, the reshaped matrix has one nonzero entry (at the all-zero row/column), so its rank is 1.
Example: ∣ W n ⟩ \lvert W_n\rangle ∣ W n ⟩ has Schmidt rank 2 across any single-edge cut. Recall
∣ W n ⟩ = 1 n ∑ j = 0 n − 1 ∣ 0 ⋯ 1 j ⋯ 0 ⟩ . \lvert W_n\rangle=\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\lvert0\cdots1_j\cdots0\rangle. ∣ W n ⟩ = n 1 j = 0 ∑ n − 1 ∣ 0 ⋯ 1 j ⋯ 0 ⟩ .
Across the cut { 0 , … , i − 1 } ∣ { i , … , n } \{0,\ldots,i-1\}\mid\{i,\ldots,n\} { 0 , … , i − 1 } ∣ { i , … , n } split the excitation “on the left” vs. “on the right”:
∣ W n ⟩ = i n ∣ L 1 ⟩ ⊗ ∣ 0 ⋯ 0 ⟩ R + n − i n ∣ 0 ⋯ 0 ⟩ L ⊗ ∣ R 1 ⟩ , \lvert W_n\rangle=\sqrt{\frac{i}{n}}\lvert L_1\rangle\otimes\lvert0\cdots0\rangle_R+\sqrt{\frac{n-i}{n}}\lvert0\cdots0\rangle_L\otimes\lvert R_1\rangle, ∣ W n ⟩ = n i ∣ L 1 ⟩ ⊗ ∣ 0 ⋯ 0 ⟩ R + n n − i ∣ 0 ⋯ 0 ⟩ L ⊗ ∣ R 1 ⟩ ,
∣ L 1 ⟩ = 1 i ∑ j = 0 i − 1 ∣ 0 ⋯ 1 j ⋯ 0 ⟩ L , ∣ R 1 ⟩ = 1 n − i ∑ j = i n − 1 ∣ 0 ⋯ 1 j ⋯ 0 ⟩ R \lvert L_1\rangle=\frac{1}{\sqrt{i}}\sum_{j=0}^{i-1}\lvert0\cdots1_j\cdots0\rangle_L,\qquad
\lvert R_1\rangle=\frac{1}{\sqrt{n-i}}\sum_{j=i}^{n-1}\lvert0\cdots1_j\cdots0\rangle_R ∣ L 1 ⟩ = i 1 j = 0 ∑ i − 1 ∣ 0 ⋯ 1 j ⋯ 0 ⟩ L , ∣ R 1 ⟩ = n − i 1 j = i ∑ n − 1 ∣ 0 ⋯ 1 j ⋯ 0 ⟩ R
are orthonormal to the respective all-zero vectors. The two product terms are orthogonal and both coefficients are nonzero for 1 ≤ i ≤ n − 1 1\leq i\leq n-1 1 ≤ i ≤ n − 1 , hence SR ( ∣ W n ⟩ ) = 2 \operatorname{SR}(\lvert W_n\rangle)=2 SR (∣ W n ⟩) = 2 . In the matrix view, the reshaped matrix has two nonzero singular values i / n \sqrt{i/n} i / n and ( n − i ) / n \sqrt{(n-i)/n} ( n − i ) / n .
Two–local and number–conserving structure
On a given block b b b with sites i ∈ { 0 , … , n − 1 } i\in\{0,\ldots,n-1\} i ∈ { 0 , … , n − 1 } , define the Pauli ladder operators
σ i + = ∣ 1 ⟩ ⟨ 0 ∣ i = 1 2 ( X i − i Y i ) , σ i − = ∣ 0 ⟩ ⟨ 1 ∣ i = 1 2 ( X i + i Y i ) . \sigma_i^{+}=\lvert1\rangle\langle0\rvert_i=\frac{1}{2}(X_i-\mathrm{i}Y_i),\qquad
\sigma_i^{-}=\lvert0\rangle\langle1\rvert_i=\frac{1}{2}(X_i+\mathrm{i}Y_i). σ i + = ∣ 1 ⟩ ⟨ 0 ∣ i = 2 1 ( X i − i Y i ) , σ i − = ∣ 0 ⟩ ⟨ 1 ∣ i = 2 1 ( X i + i Y i ) .
A straightforward calculation gives
X i X j + Y i Y j = 2 ( σ i + σ j − + σ i − σ j + ) , ( i ≠ j ) . (21) X_iX_j+Y_iY_j=2(\sigma_i^{+}\sigma_j^{-}+\sigma_i^{-}\sigma_j^{+}),\qquad(i\ne j). \tag*{(21)} X i X j + Y i Y j = 2 ( σ i + σ j − + σ i − σ j + ) , ( i = j ) . (21)
Hence the block mixer can be written (up to an overall factor 2 absorbable into the angle)
H M ( b ) : = ∑ 0 ≤ i < j ≤ n − 1 ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) = 2 ∑ 0 ≤ i < j ≤ n − 1 ( σ i + σ j − + σ i − σ j + ) . (22) H_M^{(b)} := \sum_{0\le i<j\le n-1}\left(X_i^{(b)}X_j^{(b)}+Y_i^{(b)}Y_j^{(b)}\right)=2\sum_{0\le i<j\le n-1}\left(\sigma_i^{+}\sigma_j^{-}+\sigma_i^{-}\sigma_j^{+}\right). \tag*{(22)} H M ( b ) := 0 ≤ i < j ≤ n − 1 ∑ ( X i ( b ) X j ( b ) + Y i ( b ) Y j ( b ) ) = 2 0 ≤ i < j ≤ n − 1 ∑ ( σ i + σ j − + σ i − σ j + ) . (22)
Action on the one-excitation basis. Let H 1 = span { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩ } \mathcal{H}_1=\operatorname{span}\{|e_0\rangle,\ldots,|e_{n-1}\rangle\} H 1 = span { ∣ e 0 ⟩ , … , ∣ e n − 1 ⟩} denote the one-hot subspace on the block, where ∣ e k ⟩ |e_k\rangle ∣ e k ⟩ has a single ‘1’ at position k k k . For i ≠ j i\ne j i = j ,
σ j + ∣ e i ⟩ = ∣ … 1 j , 1 i , … ⟩ , σ i − σ j + ∣ e i ⟩ = ∣ e j ⟩ , σ i + σ j − ∣ e i ⟩ = 0. \sigma_j^{+}|e_i\rangle=|\ldots1_j,1_i,\ldots\rangle,\qquad\sigma_i^{-}\sigma_j^{+}|e_i\rangle=|e_j\rangle,\qquad\sigma_i^{+}\sigma_j^{-}|e_i\rangle=0. σ j + ∣ e i ⟩ = ∣ … 1 j , 1 i , … ⟩ , σ i − σ j + ∣ e i ⟩ = ∣ e j ⟩ , σ i + σ j − ∣ e i ⟩ = 0.
Using (21) ,
( X i X j + Y i Y j ) ∣ e i ⟩ = 2 σ i − σ j + ∣ e i ⟩ = 2 ∣ e j ⟩ . (23) (X_iX_j+Y_iY_j)|e_i\rangle=2\sigma_i^{-}\sigma_j^{+}|e_i\rangle=2|e_j\rangle. \tag*{(23)} ( X i X j + Y i Y j ) ∣ e i ⟩ = 2 σ i − σ j + ∣ e i ⟩ = 2∣ e j ⟩ . (23)
By symmetry, ( X i X j + Y i Y j ) ∣ e j ⟩ = 2 ∣ e i ⟩ (X_iX_j+Y_iY_j)|e_j\rangle=2|e_i\rangle ( X i X j + Y i Y j ) ∣ e j ⟩ = 2∣ e i ⟩ , and for any k ∉ { i , j } k\notin\{i,j\} k ∈ / { i , j } , ( X i X j + Y i Y j ) ∣ e k ⟩ = 0 (X_iX_j+Y_iY_j)|e_k\rangle=0 ( X i X j + Y i Y j ) ∣ e k ⟩ = 0 . Thus, restricted to H 1 \mathcal{H}_1 H 1 , H M ( b ) H_M^{(b)} H M ( b ) acts as the (weighted) adjacency of the complete graph K n K_n K n :
H M ( b ) ∣ H 1 = 2 ∑ 0 ≤ i < j ≤ n − 1 ( ∣ e i ⟩ ⟨ e j ∣ + ∣ e j ⟩ ⟨ e i ∣ ) = 2 A ( K n ) . (24) H_M^{(b)}\big|_{\mathcal{H}_1}=2\sum_{0\le i<j\le n-1}\left(|e_i\rangle\langle e_j|+|e_j\rangle\langle e_i|\right)=2A(K_n). \tag*{(24)} H M ( b ) H 1 = 2 0 ≤ i < j ≤ n − 1 ∑ ( ∣ e i ⟩ ⟨ e j ∣ + ∣ e j ⟩ ⟨ e i ∣ ) = 2 A ( K n ) . (24)
Excitation number preservation is straight forward. Let N ^ = ∑ i = 0 n − 1 σ i + σ i − \hat{N}=\sum_{i=0}^{n-1}\sigma_i^{+}\sigma_i^{-} N ^ = ∑ i = 0 n − 1 σ i + σ i − be the excitation-number operator on the block. Each term σ i + σ j − \sigma_i^{+}\sigma_j^{-} σ i + σ j − lowers at j j j and raises at i i i , keeping the total count unchanged; likewise for its Hermitian conjugate. Hence
[ H M ( b ) , N ^ ] = 0 , [H_M^{(b)},\hat{N}]=0, [ H M ( b ) , N ^ ] = 0 ,
so H M ( b ) H_M^{(b)} H M ( b ) preserves all fixed-Hamming-weight sectors, in particular H 1 \mathcal{H}_1 H 1 .
Proof of Proposition 12
Proof. Step 1 (Representation on H 1 \mathcal{H}_1 H 1 ). With basis { ∣ e k ⟩ } k = 0 n − 1 \{|e_k\rangle\}_{k=0}^{n-1} { ∣ e k ⟩ } k = 0 n − 1 , the XY terms act as
H i j ( b ) ∣ H 1 = E i j + E j i , E i j : = ∣ e i ⟩ ⟨ e j ∣ , H_{ij}^{(b)}\big|_{\mathcal{H}_1}=E_{ij}+E_{ji},\qquad E_{ij}:=|e_i\rangle\langle e_j|, H ij ( b ) H 1 = E ij + E j i , E ij := ∣ e i ⟩ ⟨ e j ∣ ,
and H Z ( 1 ) ∣ H 1 = D : = ∑ k = 0 n − 1 d k E k k H_Z^{(1)}\big|_{\mathcal{H}_1}=D:=\sum_{k=0}^{n-1}d_kE_{kk} H Z ( 1 ) H 1 = D := ∑ k = 0 n − 1 d k E k k is diagonal. “Nontrivial” means D ∝̸ I D\not\propto I D ∝ I .
Step 2 (Skew-symmetric off-diagonals). For any pair ( i , j ) (i,j) ( i , j ) with d i ≠ d j d_i\ne d_j d i = d j ,
[ D , E i j + E j i ] = ( d i − d j ) ( E i j − E j i ) , [D,E_{ij}+E_{ji}]=(d_i-d_j)(E_{ij}-E_{ji}), [ D , E ij + E j i ] = ( d i − d j ) ( E ij − E j i ) ,
so E i j − E j i E_{ij}-E_{ji} E ij − E j i lies in the Lie closure L : = Lie { i G } \mathcal{L}:=\operatorname{Lie}\{i\mathcal{G}\} L := Lie { i G } .
Step 3 (Traceless diagonals). With S i j : = E i j + E j i S_{ij}:=E_{ij}+E_{ji} S ij := E ij + E j i and A i j : = E i j − E j i A_{ij}:=E_{ij}-E_{ji} A ij := E ij − E j i obtained as above for some pair ( i , j ) (i,j) ( i , j ) with d i ≠ d j d_i\ne d_j d i = d j , compute
[ S i j , A i j ] = 2 ( E i i − E j j ) ∈ L . [S_{ij},A_{ij}]=2(E_{ii}-E_{jj})\in\mathcal{L}. [ S ij , A ij ] = 2 ( E ii − E j j ) ∈ L .
Hence Δ i j : = E i i − E j j ∈ L \Delta_{ij}:=E_{ii}-E_{jj}\in\mathcal{L} Δ ij := E ii − E j j ∈ L for at least one ( i , j ) (i,j) ( i , j ) . Since commutators of such Δ \Delta Δ ’s generate the linear span of all traceless diagonals, we can obtain
span { E i i − E j j : i ≠ j } ⊆ L . \operatorname{span}\{E_{ii}-E_{jj}:i\ne j\}\subseteq\mathcal{L}. span { E ii − E j j : i = j } ⊆ L .
Step 4 (All skew-symmetric off-diagonals). Given any k ≠ ℓ k\ne\ell k = ℓ , use the available XY generator S k ℓ = E k ℓ + E ℓ k ∈ L S_{k\ell}=E_{k\ell}+E_{\ell k}\in\mathcal{L} S k ℓ = E k ℓ + E ℓ k ∈ L and a traceless diagonal that separates k k k and ℓ \ell ℓ , namely Δ k ℓ = E k k − E ℓ ℓ ∈ L \Delta_{k\ell}=E_{kk}-E_{\ell\ell}\in\mathcal{L} Δ k ℓ = E k k − E ℓℓ ∈ L from Step 3, to get
[ Δ k ℓ , S k ℓ ] = 2 ( E k ℓ − E ℓ k ) ∈ L . [\Delta_{k\ell},S_{k\ell}]=2(E_{k\ell}-E_{\ell k})\in\mathcal{L}. [ Δ k ℓ , S k ℓ ] = 2 ( E k ℓ − E ℓ k ) ∈ L .
Thus for every k ≠ ℓ k\ne\ell k = ℓ we have both S k ℓ S_{k\ell} S k ℓ and A k ℓ A_{k\ell} A k ℓ .
Step 5 (Lie algebra identification). The set
{ i ( E k ℓ + E ℓ k ) , i ( E k ℓ − E ℓ k ) ( k < ℓ ) ; i ( E k k − E ℓ ℓ ) ( k < ℓ ) } \{i(E_{k\ell}+E_{\ell k}),\ i(E_{k\ell}-E_{\ell k})\ (k<\ell);\ i(E_{kk}-E_{\ell\ell})\ (k<\ell)\} { i ( E k ℓ + E ℓ k ) , i ( E k ℓ − E ℓ k ) ( k < ℓ ) ; i ( E k k − E ℓℓ ) ( k < ℓ )}
spans s u ( n ) \mathfrak{su}(n) su ( n ) . Steps 3–4 show all these elements lie in L \mathcal{L} L , hence L = s u ( n ) \mathcal{L}=\mathfrak{su}(n) L = su ( n ) .
Step 6 (Synthesis). By standard Lie–algebraic controllability (e.g., [59 ] ), the connected Lie group generated by exponentials of elements in i G i\mathcal{G} i G has Lie algebra s u ( n ) \mathfrak{su}(n) su ( n ) , hence equals S U ( n ) \mathrm{SU}(n) SU ( n ) . Density plus compactness of S U ( n ) \mathrm{SU}(n) SU ( n ) yields the stated approximation of any V ∈ S U ( n ) V\in\mathrm{SU}(n) V ∈ SU ( n ) by a finite product of exp ( − i θ H ) \exp(-i\theta H) exp ( − i θ H ) with H ∈ G H\in\mathcal{G} H ∈ G to arbitrary precision ε > 0 \varepsilon>0 ε > 0 .
On the Moment-operator gap used in the proof
For one random layer U U U , define the second-moment operator
M 2 : = E [ U ⊗ 2 ⊗ U ‾ ⊗ 2 ] . M_2 := \mathbb{E}\left[U^{\otimes2} \otimes\overline{U}^{\otimes2}\right]. M 2 := E [ U ⊗ 2 ⊗ U ⊗ 2 ] .
This is the averaging operator that governs the evolution of second moments under the circuit ensemble. The corresponding Haar benchmark is
M 2 H a a r : = ∫ U ( d ) V ⊗ 2 ⊗ V ‾ ⊗ 2 d μ H a a r ( V ) , d = n m , M_2^{\mathrm{Haar}} := \int_{U(d)} V^{\otimes2} \otimes\overline{V}^{\otimes2}\,\mathrm{d}\mu_{\mathrm{Haar}}(V), \qquad d=n^m, M 2 Haar := ∫ U ( d ) V ⊗ 2 ⊗ V ⊗ 2 d μ Haar ( V ) , d = n m ,
which is the projector onto the invariant subspace of the two-copy representation.
In this language, the moment-operator gap is the spectral gap of M 2 M_2 M 2 away from the Haar-fixed subspace. More precisely, if λ ∗ \lambda_\ast λ ∗ denotes the largest nontrivial eigenvalue of M 2 M_2 M 2 in magnitude on the orthogonal complement of the Haar-invariant space, then
Δ 2 : = 1 − λ ∗ . \Delta_2 := 1-\lambda_\ast. Δ 2 := 1 − λ ∗ .
Equivalently, when the reduced dynamics is represented by a reversible Markov kernel, one may write
Δ 2 = 1 − λ 2 , \Delta_2 = 1-\lambda_2, Δ 2 = 1 − λ 2 ,
where λ 2 \lambda_2 λ 2 is the second-largest eigenvalue. A positive lower bound on Δ 2 \Delta_2 Δ 2 implies exponential convergence of iterated moments:
∥ M 2 L − M 2 H a a r ∥ ≤ ( 1 − Δ 2 ) L , \left\|M_2^L-M_2^{\mathrm{Haar}}\right\| \leq(1-\Delta_2)^L, M 2 L − M 2 Haar ≤ ( 1 − Δ 2 ) L ,
up to the perturbative error inherited from the per-block approximate 2-designs.
In the present construction, the local block twirls reduce the relevant second-moment space to the commutant basis
{ I , S W A P } m . \{I,\mathrm{SWAP}\}^m. { I , SWAP } m .
After this reduction, the action of one layer is encoded by an induced Markov kernel on { I , S W A P } m \{I,\mathrm{SWAP}\}^m { I , SWAP } m . Thus, in the proof, the moment-operator gap can be identified with the spectral gap of this reduced kernel, provided the reduction preserves the Haar fixed space and the nontrivial sector. Under connectivity of the block-interaction graph and mild randomness in the entangling layer, this is the standard mechanism by which one obtains inverse-polynomial mixing and hence convergence to an approximate global unitary 2-design [20 , 55 ] . Therefore, more precisely, the proof uses a second-moment spectral-gap argument as follows: first identify the fixed space with the Haar second moment, then show that the remaining spectrum is bounded away from 1 by at least an inverse polynomial. This gap is exactly what yields the depth bound
L = O ( Δ 2 − 1 log ( 1 / ε g l o b ) ) . L=O\left(\Delta_2^{-1}\log(1/\varepsilon_{\mathrm{glob}})\right). L = O ( Δ 2 − 1 log ( 1/ ε glob ) ) .
up to the approximation error of the local block designs.
A derivation of the single-target second moment under a unitary 2-design
Let D D D be the dimension of the encoded Hilbert space. Fix a normalized input state
∣ ϕ ⟩ ∈ H O H |\phi\rangle\in\mathcal{H}_{\mathrm{OH}} ∣ ϕ ⟩ ∈ H OH
and a fixed target basis state
∣ x ⋆ ⟩ ∈ H O H . |x^\star\rangle\in\mathcal{H}_{\mathrm{OH}}. ∣ x ⋆ ⟩ ∈ H OH .
Let
X : = ∣ ⟨ x ⋆ ∣ U ∣ ϕ ⟩ ∣ 2 , X := \left|\langle x^\star|U|\phi\rangle\right|^2, X := ∣ ⟨ x ⋆ ∣ U ∣ ϕ ⟩ ∣ 2 ,
where U U U is drawn either from Haar measure on U ( D ) U(D) U ( D ) or from an exact unitary 2-design.
Define the rank-one projectors
ρ : = ∣ ϕ ⟩ ⟨ ϕ ∣ , Π x ⋆ : = ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ . \rho:= \lvert\phi\rangle\langle\phi\rvert, \qquad\Pi_{x^\star} := \lvert x^\star\rangle\langle x^\star\rvert. ρ := ∣ ϕ ⟩ ⟨ ϕ ∣ , Π x ⋆ := ∣ x ⋆ ⟩ ⟨ x ⋆ ∣ .
Then
X = Tr ( Π x ⋆ U ρ U † ) . (25) X = \operatorname{Tr}\left(\Pi_{x^\star} U \rho U^\dagger\right). \tag*{(25)} X = Tr ( Π x ⋆ U ρ U † ) . (25)
First moment. For Haar measure, or any exact unitary 1-design,
E U [ U ρ U † ] = I D . \mathbb{E}_{U}\left[U \rho U^\dagger\right] = \frac{I}{D}. E U [ U ρ U † ] = D I .
Hence
E [ X ] = E U [ Tr ( Π x ⋆ U ρ U † ) ] = Tr ( Π x ⋆ E U [ U ρ U † ] ) = Tr ( Π x ⋆ I D ) = Tr ( Π x ⋆ ) D = 1 D . (26) \mathbb{E}[X] = \mathbb{E}_{U}\left[\operatorname{Tr}\left(\Pi_{x^\star} U \rho U^\dagger\right)\right] = \operatorname{Tr}\left(\Pi_{x^\star}\mathbb{E}_{U}\left[U \rho U^\dagger\right]\right)
= \operatorname{Tr}\left(\Pi_{x^\star}\frac{I}{D}\right) = \frac{\operatorname{Tr}(\Pi_{x^\star})}{D} = \frac{1}{D}. \tag*{(26)} E [ X ] = E U [ Tr ( Π x ⋆ U ρ U † ) ] = Tr ( Π x ⋆ E U [ U ρ U † ] ) = Tr ( Π x ⋆ D I ) = D Tr ( Π x ⋆ ) = D 1 . (26)
Second moment. Starting from (25) ,
X 2 = Tr ( Π x ⋆ U ρ U † ) 2 . X^2 = \operatorname{Tr}\left(\Pi_{x^\star} U \rho U^\dagger\right)^2. X 2 = Tr ( Π x ⋆ U ρ U † ) 2 .
Using the tensor-product trace identity
Tr ( A ) Tr ( B ) = Tr ( A ⊗ B ) , \operatorname{Tr}(A)\operatorname{Tr}(B) = \operatorname{Tr}(A \otimes B), Tr ( A ) Tr ( B ) = Tr ( A ⊗ B ) ,
we obtain
X 2 = Tr ( Π x ⋆ U ρ U † ) Tr ( Π x ⋆ U ρ U † ) = Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) ( U ρ U † ) ⊗ 2 ) . (27) \begin{aligned}
X^2 &= \operatorname{Tr}\left(\Pi_{x^\star} U \rho U^\dagger\right)\operatorname{Tr}\left(\Pi_{x^\star} U \rho U^\dagger\right) \\
&= \operatorname{Tr}\left((\Pi_{x^\star} \otimes\Pi_{x^\star})(U \rho U^\dagger)^{\otimes2}\right). \tag*{(27)}
\end{aligned} X 2 = Tr ( Π x ⋆ U ρ U † ) Tr ( Π x ⋆ U ρ U † ) = Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) ( U ρ U † ) ⊗ 2 ) . (27)
Therefore
E [ X 2 ] = Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) E U [ ( U ρ U † ) ⊗ 2 ] ) . (28) \mathbb{E}[X^2] = \operatorname{Tr}\left((\Pi_{x^\star} \otimes\Pi_{x^\star})\mathbb{E}_{U}\left[(U \rho U^\dagger)^{\otimes2}\right]\right). \tag*{(28)} E [ X 2 ] = Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) E U [ ( U ρ U † ) ⊗ 2 ] ) . (28)
For Haar measure, or any exact unitary 2-design,
E U [ ( U ρ U † ) ⊗ 2 ] = I + F D ( D + 1 ) . (29) \mathbb{E}_{U}\left[(U \rho U^\dagger)^{\otimes2}\right] = \frac{I + F}{D(D+1)}. \tag*{(29)} E U [ ( U ρ U † ) ⊗ 2 ] = D ( D + 1 ) I + F . (29)
where F F F is the swap operator,
F ( ∣ a ⟩ ⊗ ∣ b ⟩ ) = ∣ b ⟩ ⊗ ∣ a ⟩ . F(\lvert a\rangle\otimes\lvert b\rangle) = \lvert b\rangle\otimes\lvert a\rangle. F (∣ a ⟩ ⊗ ∣ b ⟩) = ∣ b ⟩ ⊗ ∣ a ⟩ .
Substituting (29) into (28) gives
E [ X 2 ] = 1 D ( D + 1 ) Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) ( I + F ) ) = 1 D ( D + 1 ) [ Tr ( Π x ⋆ ⊗ Π x ⋆ ) + Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) F ) ] . (30) \begin{aligned}
\mathbb{E}[X^2] &= \frac{1}{D(D+1)}\operatorname{Tr}\left((\Pi_{x^\star} \otimes\Pi_{x^\star})(I+F)\right) \\
&= \frac{1}{D(D+1)}\left[\operatorname{Tr}(\Pi_{x^\star} \otimes\Pi_{x^\star}) + \operatorname{Tr}((\Pi_{x^\star} \otimes\Pi_{x^\star})F)\right]. \tag*{(30)}
\end{aligned} E [ X 2 ] = D ( D + 1 ) 1 Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) ( I + F ) ) = D ( D + 1 ) 1 [ Tr ( Π x ⋆ ⊗ Π x ⋆ ) + Tr (( Π x ⋆ ⊗ Π x ⋆ ) F ) ] . (30)
Now evaluate the two traces separately.
First, since Π x ⋆ \Pi_{x^\star} Π x ⋆ is rank one,
Tr ( Π x ⋆ ⊗ Π x ⋆ ) = Tr ( Π x ⋆ ) 2 = 1. (31) \operatorname{Tr}(\Pi_{x^\star} \otimes\Pi_{x^\star}) = \operatorname{Tr}(\Pi_{x^\star})^2 = 1. \tag*{(31)} Tr ( Π x ⋆ ⊗ Π x ⋆ ) = Tr ( Π x ⋆ ) 2 = 1. (31)
Second, use the standard identity
Tr ( ( A ⊗ B ) F ) = Tr ( A B ) . \operatorname{Tr}((A \otimes B)F) = \operatorname{Tr}(AB). Tr (( A ⊗ B ) F ) = Tr ( A B ) .
With A = B = Π x ⋆ A = B = \Pi_{x^\star} A = B = Π x ⋆ , this gives
Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) F ) = Tr ( Π x ⋆ 2 ) = Tr ( Π x ⋆ ) = 1. (32) \operatorname{Tr}((\Pi_{x^\star} \otimes\Pi_{x^\star})F) = \operatorname{Tr}(\Pi_{x^\star}^2) = \operatorname{Tr}(\Pi_{x^\star}) = 1. \tag*{(32)} Tr (( Π x ⋆ ⊗ Π x ⋆ ) F ) = Tr ( Π x ⋆ 2 ) = Tr ( Π x ⋆ ) = 1. (32)
Substituting (31) and (32) into (30) , we obtain
E [ X 2 ] = 2 D ( D + 1 ) . (33) \mathbb{E}[X^2] = \frac{2}{D(D+1)}. \tag*{(33)} E [ X 2 ] = D ( D + 1 ) 2 . (33)
Paley–Zygmund consequence. Using (26) and (33) , Paley–Zygmund gives
Pr [ X ≥ 1 2 D ] ≥ ( E [ X ] − 1 2 D ) 2 E [ X 2 ] = ( 1 / 2 D ) 2 2 / ( D ( D + 1 ) ) = D + 1 8 D = Ω ( 1 ) . (34) \Pr\left[X \ge\frac{1}{2D}\right] \ge\frac{\left(\mathbb{E}[X]-\frac{1}{2D}\right)^2}{\mathbb{E}[X^2]}
= \frac{(1/2D)^2}{2/(D(D+1))} = \frac{D+1}{8D} = \Omega(1). \tag*{(34)} Pr [ X ≥ 2 D 1 ] ≥ E [ X 2 ] ( E [ X ] − 2 D 1 ) 2 = 2/ ( D ( D + 1 )) ( 1/2 D ) 2 = 8 D D + 1 = Ω ( 1 ) . (34)
Approximate 2-design overlap. If U is an ε \varepsilon ε -approximate unitary 2-design on the encoded space, then the second-moment operator differs from the Haar value by an error term Δ ε \Delta_\varepsilon Δ ε :
E U ∼ U [ ( U ρ U † ) ⊗ 2 ] = I + F D ( D + 1 ) + Δ ε , \mathbb{E}_{U\sim\mathcal{U}}\left[(U\rho U^\dagger)^{\otimes2}\right] = \frac{\mathbb{I}+\mathbb{F}}{D(D+1)}+\Delta_\varepsilon, E U ∼ U [ ( U ρ U † ) ⊗ 2 ] = D ( D + 1 ) I + F + Δ ε ,
with ∥ Δ ε ∥ \|\Delta_\varepsilon\| ∥ Δ ε ∥ controlled by the approximation parameter in the norm specified by the design theorem. In that case,
E [ X 2 ] = Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) [ I + F D ( D + 1 ) + Δ ε ] ) = 2 D ( D + 1 ) + Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) Δ ε ) = 2 D ( D + 1 ) ± O ( ε ) , (35) \mathbb{E}[X^2]=\operatorname{Tr}\left((\Pi_{x^\star}\otimes\Pi_{x^\star})\left[\frac{\mathbb{I}+\mathbb{F}}{D(D+1)}+\Delta_\varepsilon\right]\right)
= \frac{2}{D(D+1)}+\operatorname{Tr}((\Pi_{x^\star}\otimes\Pi_{x^\star})\Delta_\varepsilon)
= \frac{2}{D(D+1)}\pm O(\varepsilon), \tag*{(35)} E [ X 2 ] = Tr ( ( Π x ⋆ ⊗ Π x ⋆ ) [ D ( D + 1 ) I + F + Δ ε ] ) = D ( D + 1 ) 2 + Tr (( Π x ⋆ ⊗ Π x ⋆ ) Δ ε ) = D ( D + 1 ) 2 ± O ( ε ) , (35)
where the implicit constant depends on the precise definition of approximate 2-design and the norm in which the deviation is controlled. Similarly,
E [ X ] = 1 D ± O ( ε ) . \mathbb{E}[X]=\frac{1}{D}\pm O(\varepsilon). E [ X ] = D 1 ± O ( ε ) .
Rank-S S S projector version
The same calculation applies when the rank-one target projector Π x ⋆ \Pi_{x^\star} Π x ⋆ is replaced by a projector P P P of rank S S S , for example the feasible projector P Π P_\Pi P Π .
Define
Y : = ⟨ ϕ ∣ U † P U ∣ ϕ ⟩ = Tr ( P U ρ U † ) . Y:=\langle\phi|U^\dagger P U|\phi\rangle=\operatorname{Tr}(P U\rho U^\dagger). Y := ⟨ ϕ ∣ U † P U ∣ ϕ ⟩ = Tr ( P U ρ U † ) .
Then
E [ Y ] = S D , \mathbb{E}[Y]=\frac{S}{D}, E [ Y ] = D S ,
and
E [ Y 2 ] = Tr ( ( P ⊗ P ) I + F D ( D + 1 ) ) = Tr ( P ⊗ P ) + Tr ( ( P ⊗ P ) F ) D ( D + 1 ) = ( Tr P ) 2 + Tr ( P 2 ) D ( D + 1 ) . (36) \mathbb{E}[Y^2]=\operatorname{Tr}\left((P\otimes P)\frac{\mathbb{I}+\mathbb{F}}{D(D+1)}\right)
=\frac{\operatorname{Tr}(P\otimes P)+\operatorname{Tr}((P\otimes P)\mathbb{F})}{D(D+1)}
=\frac{(\operatorname{Tr}P)^2+\operatorname{Tr}(P^2)}{D(D+1)}. \tag*{(36)} E [ Y 2 ] = Tr ( ( P ⊗ P ) D ( D + 1 ) I + F ) = D ( D + 1 ) Tr ( P ⊗ P ) + Tr (( P ⊗ P ) F ) = D ( D + 1 ) ( Tr P ) 2 + Tr ( P 2 ) . (36)
If P P P is a projector of rank S S S , then
Tr ( P ) = S , Tr ( P 2 ) = S , \operatorname{Tr}(P)=S,\qquad\operatorname{Tr}(P^2)=S, Tr ( P ) = S , Tr ( P 2 ) = S ,
so
E [ Y 2 ] = S 2 + S D ( D + 1 ) . (37) \mathbb{E}[Y^2]=\frac{S^2+S}{D(D+1)}. \tag*{(37)} E [ Y 2 ] = D ( D + 1 ) S 2 + S . (37)
In particular,
E [ Y 2 ] = ( S D ) 2 1 + 1 / S 1 + 1 / D ≤ 2 ( S D ) 2 \mathbb{E}[Y^2]=\left(\frac{S}{D}\right)^2\frac{1+1/S}{1+1/D}\le2\left(\frac{S}{D}\right)^2 E [ Y 2 ] = ( D S ) 2 1 + 1/ D 1 + 1/ S ≤ 2 ( D S ) 2