betaFeedback

WorksComputer Science

Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

Abstract

We introduce the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), a shallow, constraint-aware ansatz that operates inside the one-hot product space [n]^m, where m is the number of blocks and each block is initialized in an n-qubit W_n state. We give an ancilla-free, depth-optimal encoder that prepares W_n using n-1 two-qubit rotations per block, and a two-local block-XY mixer that preserves the one-hot manifold and has a constant spectral gap on the one-excitation sector. At the level of expressivity, we establish per-block controllability, implying approximate universality per block. At the level of distributional behavior, we show that, after natural block and symbol permutation twirls, shallow CE-QAOA realizes an encoded unitary 1-design and supports approximate second-moment (2-design) behavior; combined with a Paley-Zygmund argument, this yields finite-shot anticoncentration guarantees. Algorithmically, we wrap constant-depth sampling with a deterministic feasibility checker to obtain a polynomial-time hybrid quantum-classical solver (PHQC) that returns the best observed feasible solution in O(S n^2) time, where S is a polynomial shot budget. We obtain two advantages. First, when CE-QAOA fixes r >= 1 locations different from the start city, we achieve a Theta(n^r) reduction in shot complexity even against a classical sampler that draws uniformly from the feasible set. Second, against a classical baseline restricted to raw bitstring sampling, we show an exp(Theta(n^2)) minimax separation. In noiseless circuit simulations of traveling salesman problem instances with n in {4,...,10} locations from the QOPTLib benchmark library, we recover the global optimum at depth p = 1 using polynomial shot budgets and coarse parameter grids defined by the problem size.

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 WnW_n state using exactly n−1n-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- designs.

Why do unitary tt-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 tt-design reproduces Haar moments up to degree tt. Thus any degree-≤t\le 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=2t = 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 and a corresponding existence theorem for any target basis vector x⋆x^\star (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 tt-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 n2n^2 qubits are imagined to be arranged in nn blocks of size nn and the double one-hot constraint restricts to a fixed-Hamming-weight manifold containing only n!n! basis states out of the encoded nnn^n encoded basis vectors and 2n22^{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(nk)O(n^k) at depth p=1p = 1 as reported in Table 1. All plots presented in the following can be reproduced as demonstrated in [31].

InstanceCities nnShots SSAdvantage (nr)(n^r)Tour costOptimal (γ,β)(\gamma,\beta)
wi44160n1n^16,700Yes (1.57, 2.36)
wi55250n2n^26,786Yes (1.57, 2.36)
wi66360n3n^39,815Yes (2.62, 2.09)
wi77733>n3>n^37,245Yes (3.14, 2.62)
dj882.56×1042.56\times10^4>n3>n^32,762Yes (1.35, 2.24)
dj993.65×1043.65\times10^4>n4>n^42,134Yes (0.30, 1.60)
dj10101.00×1061.00\times10^6>n4>n^42,822Yes (1.01, 1.57)

Table 1. Single-layer CE-QAOA sampling with design-based angles and shot budget S=10n3−5S=10n^{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 Scl=Θ(nm−1log⁡(1/δ))S_{\mathrm{cl}}=\Theta(n^{m-1}\log(1/\delta)) holds. We set log⁡(1/δ)=10\log(1/\delta)=10 for both quantum and classical models and nrn^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 HM(b)↦A(Kn)H_{M}^{(b)} \mapsto 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 nn-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 SmS_m and symbol relabelings SnS_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) HpenH_{\mathrm{pen}} is invariant under Sm×SnS_m \times S_n, so every penalty level set Lt={x:Hpen(x):=⟨x∣Hpen∣x⟩=t}L_t = \{x : H_{\mathrm{pen}}(x) := \langle x \mid H_{\mathrm{pen}} \mid x \rangle= t\} (in particular L0L_0) is preserved setwise; and (ii) a block-permutation twirl acts transitively on the encoded basis and yields an exact unitary 1-design on HOH\mathcal{H}_{\mathrm{OH}} (Lemma 15). This exact first-moment identity directly powers our existence guarantee for the optimal basis vector x⋆x^\star (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 (L1L_1, L2L_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/Dc/D scale. Where DD is the encoded dimension and c>0c > 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 II belongs to the CE–QAOA kernel if there exist integers n,m∈Nn,m \in\mathbb{N} and the one-hot encoder E1hotE_{\mathrm{1hot}} that initializes the dynamics in the fixed–Hamming–weight space

HOH=(H1)⊗m,H1=span⁡{∣e0⟩,…,∣en−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).}

The problem Hamiltonian splits as

HC=Hpen+Hobj,H_C = H_{\mathrm{pen}} + H_{\mathrm{obj}},

Where HobjH_{\mathrm{obj}} is the Ising Hamiltonian representing the objective and only needs to be diagonal in the computational basis. HpenH_{\mathrm{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. HpenH_{\mathrm{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). Consequently, spec⁡(Hpen)⊆{0,1,…,tmax⁡}\operatorname{spec}(H_{\mathrm{pen}}) \subseteq\{0,1,\ldots,t_{\max}\} with tmax⁡=O(m)=poly⁡(n)t_{\max} = O(m) = \operatorname{poly}(n).

(b) Pattern symmetry. HpenH_{\mathrm{pen}} is invariant under (i) block permutations SmS_m and (ii) global symbol relabelings SnS_n. Hence the configuration space decomposes into level sets Lt={x:Hpen(x):=⟨x∣Hpen∣x⟩=t}L_t = \{x : H_{\mathrm{pen}}(x) := \langle x \mid H_{\mathrm{pen}} \mid x\rangle= t\} that are preserved setwise.

(c) In addition, the initial state is the +1+1 eigenstate of the block-local normalized XY mixer Hamiltonian,

H~M(b)=1n−1∑0≤j<k≤n−1(Xj(b)Xk(b)+Yj(b)Yk(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),

with ∥H~M(b)∥=O(1)\lVert\widetilde{H}^{(b)}_M\rVert= O(1) on each block. The initial state is the uniform one-hot product

∣s0⟩=∣sb⟩⊗m,∣sb⟩=1n∑k=0n−1∣ek⟩(a Wn 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).}

Although the kernel above fixes one-hot blocks (1 excitation per block), many applications naturally use kk-hot blocks (fixed Hamming weight of kk per block). In that case, one replaces H1\mathcal{H}_1 by Hk=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\}, and chooses a suitable number-conserving block-local mixer (e.g. modified XY Hamiltonian, which preserves excitation number) normalized to constant operator norm on Hk\mathcal{H}_k. The corresponding initial state becomes a tensor product of Dicke states encoders [39],

References

  1. [1]Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982.
  2. [2]Manfred Padberg and Giovanni Rinaldi. “A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Travelling Salesman Problems”. In: SIAM Review 33.1 (1991), pp. 60–100. DOI: 10.1137/1033004.DOI
  3. [3]Paolo Toth and Daniele Vigo. Vehicle Routing: Problems, Methods, and Applications. 2nd ed. MOS-SIAM Series on Optimization. SIAM, 2014. DOI: 10.1137/1.9781611973594.
  4. [4]Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. “Machine Learning for Combinatorial Optimization: A Methodological Tour d’Horizon”. In: European Journal of Operational Research 290.2 (2021), pp. 405–421. DOI: 10.1016/j.ejor.2020.07.063.DOI
  5. [5]Eugene L. Lawler and David E. Wood. “Branch-and-Bound Methods: A Survey”. In: Operations Research 14.4 (1966), pp. 699–719. DOI: 10.1287/opre.14.4.699.DOI
  6. [6]Shen Lin and Brian W. Kernighan. “An Effective Heuristic Algorithm for the Travelling-Salesman Problem”. In: Operations Research 21.2 (1973), pp. 498–516. DOI: 10.1287/opre.21.2.498.DOI
  7. [7]Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A Quantum Approximate Optimization Algorithm”. In: arXiv preprint arXiv:1411.4028 (2014).arxiv.org/abs/1411.4028
  8. [8]Juan A. Montañez-Barrera and Kristel Michielsen. Towards a Universal QAOA Protocol: Evidence of a Scaling Advantage in Solving Some Combinatorial Optimization Problems. https://arxiv.org/abs/2405.09169. 2024. arXiv: 2405.09169 [quant-ph].
  9. [9]Eunok Bae and Soojoon Lee. “Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs”. In: Quantum Information Processing 23.3 (2024), p. 78. DOI: 10.1007/s11128-024-04286-0.DOI
  10. [10]Jernej Rudi Finžgar et al. “Quantum-Informed Recursive Optimization Algorithms”. In: PRX Quantum 5.2 (May 2024), p. 020327. DOI: 10.1103/PRXQuantum.5.020327. URL: https://link.aps.org/doi/10.1103/PRXQuantum.5.020327.DOI
  11. [11]M. Cerezo et al. “Variational quantum algorithms”. In: Nature Reviews Physics 3.9 (2021), pp. 625–644. DOI: 10.1038/s42254-021-00348-9.DOI
  12. [12]J. Tilly et al. “The Variational Quantum Eigensolver: A review of methods and best practices”. In: PRX Quantum 3.3 (2022), p. 030204. DOI: 10.1103/PRXQuantum.3.030204.DOI
  13. [13]Jarrod R. McClean et al. “Barren plateaus in quantum neural network training landscapes”. In: Nature Communications 9.1 (2018), p. 4812. DOI: 10.1038/s41467-018-07090-4.
  14. [14]Stuart Hadfield et al. “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz”. In: Algorithms 12.2 (2019), p. 34. DOI: 10.3390/a12020034.DOI
  15. [15]Franz G. Fuchs and Ruben Pariente Bassa. “Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm”. In: Algorithms 15.6 (2022), p. 202. DOI: 10.3390/a15060202.DOI
  16. [16]Andreas Bärtschi and Stephan Eidenbenz. Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation. arXiv:2006.00354. 2020. DOI: 10.48550/arXiv.2006.00354.DOI
  17. [17]B. Tsvelikhovskiy, I. Safro, and Y. Alexeev. “Equivariant QAOA and the Duel of the Mixers”. In: arXiv:2405.07211 (2024). arXiv: 2405.07211 [quant-ph].arxiv.org/abs/2405.07211
  18. [18]B. Tsvelikhovskiy, I. Safro, and Y. Alexeev. “Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm”. In: arXiv preprint arXiv:2309.13787 (2023). arXiv: 2309.13787 [quant-ph].arxiv.org/abs/2309.13787
  19. [19]Ningyi Xie and Hoong Chuin Lau. A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem. arXiv:2308.08785. 2024. URL: https://arxiv.org/abs/2308.08785.
  20. [20]Fernando G. S. L. Brandão and Aram W. Harrow. “Local random quantum circuits are approximate polynomial-designs”. In: Communications in Mathematical Physics 346.2 (2016), pp. 397–434.
  21. [21]A. Pérez-Salinas, H. Wang, and X. Bonet-Monroig. “Analyzing variational quantum landscapes with information content”. In: npj Quantum Information 10 (Feb. 2024), p. 27. DOI: 10.1038/s41534-024-00819-8.
  22. [22]Stuart Hadfield, Tad Hogg, and Eleanor G. Rieffel. “Analytical framework for quantum alternating operator ansätze”. In: Quantum Science and Technology 8.1 (Dec. 2022), p. 015017. ISSN: 2058-9565. DOI: 10.1088/2058-9565/aca3ce.DOI
  23. [23]Rafael S. do Carmo et al. Warm-Starting QAOA with XY Mixers: A Novel Approach for Quantum-Enhanced Vehicle Routing Optimization. arXiv preprint arXiv:2504.19934. 2025. arXiv: 2504.19934 [quant-ph].arxiv.org/abs/2504.19934
  24. [24]Andrew Lucas. “Ising formulations of many NP problems”. In: Frontiers in Physics 2 (2014), p. 5. DOI: 10.3389/fphy.2014.00005.DOI
  25. [25]Jack Edmonds. “Paths, Trees, and Flowers”. In: Canadian Journal of Mathematics 17 (1965), pp. 449–467. DOI: 10.4153/CJM-1965-045-4.DOI
  26. [26]Harold W. Kuhn. “The Hungarian Method for the Assignment Problem”. In: Naval Research Logistics Quarterly 2.1-2 (1955), pp. 83–97. DOI: 10.1002/nav.3800020109.DOI
  27. [27]Chinonso Onah et al. “QUEST: Quantum-Enhanced Shared Transportation”. In: 2025 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 01. 2025, pp. 2149–2160. DOI: 10.1109/QCE65121.2025.00235.DOI
  28. [28]Gushua Li, Yufei Ding, and Yuan Xie. “On the Co-Design of Quantum Software and Hardware”. In: ICCAD ’21: IEEE/ACM International Conference on Computer-Aided Design. 2021. DOI: 10.1145/3477206.3477464.DOI
  29. [29]Teague Tomesh and Margaret Martonosi. “Quantum Codesign”. In: IEEE Micro 41.5 (2021), pp. 33–40. DOI: 10.1109/MM.2021.3094461.DOI
  30. [30]Eneko Osaba and Erika Villar-Rodríguez. “QOPTLib: a Quantum-Computing-Oriented Benchmark for Combinatorial Optimisation Problems”. In: Proc. Quantum Tech. 2024. 2024.
  31. [31]Chinonso Onah, Roman Firt, and Kristel Michielsen. Dataset: Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs (0.1). Version 0.1. 2025. DOI: 10.5281/zenodo.15725265. URL: https://doi.org/10.5281/zenodo.15725265.
  32. [32]Kate A. Smith-Miles et al. “The travelling salesperson problem and the challenges of near-term quantum advantage”. In: Quantum Science and Technology 10.3 (May 2025), p. 033001. DOI: 10.1088/2058-9565/add61d.
  33. [33]Nicholas Chancellor. “Circuit design for multi-body interactions in superconducting quantum annealing systems with applications to a scalable architecture”. In: npj Quantum Information (2017).DOI
  34. [34]Ryan LaRose, M. Cerezo, Piotr Czarnik, et al. “Mixer-phaser Ansätze for quantum optimization with hard constraints”. In: Quantum Machine Intelligence 4.2 (2022), p. 12. DOI: 10.1007/s42484-022-00069-x.DOI
  35. [35]Rafael S. do Carmo et al. Warm-Starting QAOA with XY Mixers: A Novel Approach for Quantum-Enhanced Vehicle Routing Optimization. 2025. arXiv: 2504.19934 [quant-ph].arxiv.org/abs/2504.19934
  36. [36]Daniel J. Egger et al. “Warm-starting quantum optimization”. In: PRX Quantum 2 (2021), p. 040348.DOI
  37. [37]Zichang He et al. “Alignment between initial state and mixer improves QAOA performance for constrained optimization”. In: npj Quantum Information 9.1 (Nov. 2023). ISSN: 2056-6387. DOI: 10.1038/s41534-023-00787-5. URL: https://doi.org/10.1038/s41534-023-00787-5.
  38. [38]Zhihui Wang et al. “XY mixers: Analytical and numerical results for the quantum approximate optimization algorithm”. In: Physical Review A 101.1 (2020), p. 012320. DOI: 10.1103/PhysRevA.101.012320.DOI
  39. [39]Andreas Bärtschi and Stephan Eidenbenz. “Deterministic Preparation of Dicke States”. In: Fundamentals of Computation Theory. Springer International Publishing, 2019, pp. 126–139. ISBN: 9783030250270. DOI: 10.1007/978-3-030-25027-0_9.
  40. [40]Eugene L. Lawler et al. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985.
  41. [41]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  42. [42]Tjalling C. Koopmans and Martin Beckmann. “Assignment Problems and the Location of Economic Activities”. In: Econometrica 25.1 (1957), pp. 53–76. DOI: 10.2307/1907742.DOI
  43. [43]E. M. Loiola et al. “A Survey for the Quadratic Assignment Problem”. In: European Journal of Operational Research 176.2 (2007), pp. 657–690. DOI: 10.1016/j.ejor.2005.09.032.
  44. [44]Sartaj Sahni and Teofilo Gonzalez. “P-Complete Approximation Problems”. In: Journal of the ACM 23.3 (1976), pp. 555–565. DOI: 10.1145/321958.321975.DOI
  45. [45]Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.DOI
  46. [46]Richard M. Karp. “Reducibility among Combinatorial Problems”. In: Complexity of Computer Computations. Plenum, 1972, pp. 85–103.
  47. [47]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979.
  48. [48]Michael R. Garey, David S. Johnson, and Ravi Sethi. “The Complexity of Flow-shop and Jobshop Scheduling”. In: Mathematics of Operations Research 1.2 (1976), pp. 117–129. DOI: 10.1287/moor.1.2.117.DOI
  49. [49]Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and Peter Brucker. “Complexity of Machine Scheduling Problems”. In: Annals of Discrete Mathematics 1 (1977), pp. 343–362. DOI: 10.1016/S0167-5060(08)70743-X.DOI
  50. [50]James Munkres. “Algorithms for the Assignment and Transportation Problems”. In: Journal of the Society for Industrial and Applied Mathematics 5.1 (1957), pp. 32–38. DOI: 10.1137/0105003.DOI
  51. [51]Firat Diker. Deterministic construction of arbitrary W states with quadratically increasing number of two-qubit gates. 2022. arXiv: 1606.09290 [quant-ph]. URL: https://arxiv.org/abs/1606.09290.
  52. [52]M. Ayrton et al. Qiskit: An Open-source Framework for Quantum Computing. Version 0.47. 2023. URL: https://qiskit.org.
  53. [53]S. Bravyi and D. Gosset. “Improved classical simulation of quantum circuits dominated by Clifford gates”. In: Phys. Rev. Lett. 116 (2016), p. 250501.DOI
  54. [54]Chris Godsil and Gordon Royle. Algebraic Graph Theory. Vol. 207. Graduate Texts in Mathematics. New York: Springer, 2001.DOI
  55. [55]Jean Bourgain and Alex Gamburd. “A Spectral Gap Theorem in SU(d)”. In: J. Eur. Math. Soc. 14.5 (2012), pp. 1455–1511.arxiv.org/abs/1108.6264
  56. [56]Guifré Vidal. “Efficient Classical Simulation of Slightly Entangled Quantum Computations”. In: Phys. Rev. Lett. 91.14 (2003), p. 147902. DOI: 10.1103/PhysRevLett.91.147902.DOI
  57. [57]David L. Applegate et al. The Traveling Salesman Problem: A Computational Study. Princeton, NJ: Princeton University Press, 2007.
  58. [58]Richard Bellman. “Dynamic Programming Treatment of the Traveling Salesman Problem”. In: Journal of the ACM 9.1 (1962), pp. 61–63. DOI: 10.1145/321105.321111.DOI
  59. [59]Domenico D’Alessandro. Introduction to Quantum Control and Dynamics. Boca Raton, FL: CRC Press, 2007.

Paper details

vlnc:W_wuz8fraj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents