PaperlayerView exact revision on arXiv

Source-linked AI summary

Domain wall encoding of discrete variables for quantum annealing and QAOA

Nicholas Chancellor

arXiv:1903.05068v4quant-ph

TL;DR

Arbitrary interactions between higher-than-binary variables are costly to represent with binary encodings, while limited hardware connectivity adds embedding overhead. The paper develops domain-wall encodings for quantum annealing and QAOA, then compares their embedding with one-hot encoding. Domain-wall embedding performs similarly or better in the reported cases, with gains dependent on problem structure.

  • Problem

    Arbitrary interactions between higher-than-binary variables require costly higher-order terms in binary encodings, and limited connectivity makes embedding a concern for quantum hardware.

    Source: §I · p. 2

  • Method

    The paper encodes discrete variables and their interactions using one-dimensional Ising domain walls for applications to quantum annealing and QAOA.

    Source: §I · pp. 1, 3

  • Results

    Domain-wall embedding is similar or better than one-hot in the examined structured problems, with scheduling gains in Pegasus comparable to those from Pegasus versus chimera and outcomes dependent on problem structure.

    Source: §I · p. 3, B. Graph Coloring · p. 9, §X · p. 13

  • Takeaways & Limitations

    Domain-wall structure can support discrete or mixed binary/integer problems designed for hardware with no embedding overhead.

    Source: §X · p. 13

Abstract

from arXiv · show

In this paper I propose a new method of encoding discrete variables into Ising model qubits for quantum optimization. The new method is based on the physics of domain walls in one dimensional Ising spin chains. I find that these encodings and the encoding of arbitrary two variable interactions is possible with only two body Ising terms. Following on from similar results for the `one hot' method of encoding discrete variables [Hadfield et. al. Algorithms 12.2 (2019): 34] I also demonstrate that it is possible to construct two body mixer terms which do not leave the logical subspace, an important consideration for optimising using the quantum alternating operator ansatz (QAOA). I additionally discuss how, since the couplings in the domain wall encoding only need to be ferromagnetic and therefore could in principle be much stronger than anti-ferromagnetic couplers, application specific quantum annealers for discrete problems based on this construction may be beneficial. Finally, I compare embedding for synthetic scheduling and colouring problems with the domain wall and one hot encodings on two graphs which are relevant for quantum annealing, the chimera graph and the Pegasus graph. For every case I examine I find a similar or better performance from the domain wall encoding as compared to one hot, but this advantage is highly dependent on the structure of the problem. For encoding some problems, I find an advantage similar to the one found by embedding in a Pegasus graph compared to embedding in a chimera graph.

I. INTRODUCTION AND BACKGROUND

The paper proposes domain-wall encoding as an alternative to one-hot encoding for discrete optimization, targeting implementation costs from limited hardware connectivity. It develops the approach for quantum annealing and QAOA and compares its embedding efficiency with one-hot encoding.

I. INTRODUCTION AND BACKGROUND

  • The paper considers both quantum annealing and gate-model QAOA, noting that mapping techniques may be useful across the two settings.QAOA is restricted to gate-model implementations in this discussion.Source: §I · pp. 1–2
  • Limited connectivity motivates embedding, but minor embedding and parity encoding both reduce usable qubit capacity and effective energy dynamic range.The paper bases its analysis on minor embedding, described as the most common experimental mapping technique.Source: §I · p. 2
  • Pegasus is described as more connected than chimera, although its hardware topology was not yet publicly available in the paper's account.Pegasus graphs of various sizes could be generated using the publicly available D-Wave networkx package.Source: §I · p. 2
  • Discrete variables arise in problems such as scheduling and graph colouring, while arbitrary interactions make binary encoding costly and one-hot encoding a traditional alternative.Binary encoding is preferable for quadratic interactions, but arbitrary interactions require higher-order terms; one-hot uses m qubits per variable and needs no additional qubits for two-variable interactions.Source: §I · p. 2
  • One-hot encoding uses a sufficiently large positive penalty to favor logically valid states, and arbitrary pairwise interactions between one-hot variables can use two-body Ising interactions.The penalty is described as enforcing the logically valid subspace with high probability.Source: §I · pp. 2–3
  • A single large Z_m variable is a unary encoding and is not efficient, while multiple variables have a robust tensor-product structure when sufficiently numerous relative to typical variable size.The passage conditions efficient use on having sufficiently many variables compared with the typical variable size.Source: §I · p. 3
  • Domain-wall encoding is proposed as an alternative to one-hot, with potentially fewer qubits and more efficient embedding for some realistically structured problems.The reported advantage depends on problem structure; in some cases it is comparable to the advantage of Pegasus over chimera.Source: §I · p. 3

II. DOMAIN WALLS IN THE ONE DIMENSIONAL ISING MODEL

The section encodes a discrete variable through the location of a single domain wall in a ferromagnetic Ising chain. Although the state storage is unary, the encoding’s novelty is how it supports processing, especially interactions between variables.

Domain-wall dynamics

  • A single bit flip cannot remove one domain wall; removal requires it to encounter another, preserving odd wall parity between oppositely fixed ends.The paper describes this as topological stability.Source: §II · p. 3

Domain-wall encoding

  • Fixed endpoint spins make a single domain wall at any of N+1 chain positions encode a value in ZN+1.The lowest-energy states have one wall between successive qubits.Source: §II · p. 4
  • Location penalties assign arbitrary energies to domain-wall positions; the resulting storage is unary, and the novelty lies in processing rather than storage.The domain-wall formalism recovers the standard binary qubit representation when N = 1.Source: §II · p. 4
  • An alternative definition of the domain-wall indicator requires four-body Ising interactions to implement arbitrary two-variable interactions.The paper favors its chosen definition because it avoids that requirement.Source: §II · p. 4

III. INTERACTIONS BETWEEN DOMAIN WALL VARIABLES

The section constructs arbitrary interactions between domain-wall-encoded variables from domain-wall location indicators. With the chosen definition, these interactions use two-body Ising terms, while an alternative definition requires four-body couplers.

Interaction construction

  • Arbitrary two-variable functions between ZN+1 and ZM+1 variables use at most N×M two-body Ising terms, including mixed binary/discrete couplings.The construction uses indicators for each pair of variable values.Source: §III · pp. 4–5

Degrees of freedom

  • The interaction has nm−1 independent physical degrees of freedom; the missing degree of freedom is an energy-zero shift that does not affect physical dynamics or solution ordering.The paper calls this the densest possible encoding of arbitrary integer interactions using one- and two-body Ising terms without auxiliary qubits.Source: §III · p. 5

Alternative definition

  • Using the alternative domain-wall indicator definition makes the interaction require a four-body coupler.The paper therefore uses the definition that permits two-body coupling.Source: §III · p. 5

IV. QAOA MIXERS

The proposed QAOA mixer preserves the domain-wall-valid subspace by flipping a qubit only when its neighbors differ. Its transition structure differs from one-hot mixing, and which approach performs better remains an open, problem-dependent question.

IV. QAOA MIXERS

  • The mixer flips a qubit only when it is adjacent to a single domain wall, conserving domain-wall number and keeping states within the logical subspace.The terms can be split into even- and odd-qubit commuting Hamiltonians, each of which also conserves domain-wall number.Source: §IV · pp. 5–6
  • The mixer can be constructed from two-body Ising terms already used for phase separators, together with Hadamards.Its even- and odd-qubit components are built from commuting terms.Source: §IV · pp. 5–6
  • The mixer’s conditional bit flip depends on whether two neighboring qubits agree or differ, unlike the single-qubit control in the related controlled-X-rotation mixer.The later split into commuting parts is essentially the same as in.Source: §IV · p. 6
  • Unlike one-hot mixers that allow transitions between any valid states, domain-wall mixers connect only consecutive states; which performs better remains an open, problem-dependent question.The passage notes that the implications of low dimensionality for optimization are unclear, and that one-hot mixer connectivity may also be problematic.Source: §IV · p. 6

V. SPECIALIZED DISCRETE OPTIMIZATION ANNEALERS

The domain-wall variable-encoding Hamiltonian uses only single-body fields and ferromagnetic couplings, which may suit specialized discrete-problem annealers. The proposed hardware benefits depend on driver design and on identifying valuable problems with shared structure.

V. SPECIALIZED DISCRETE OPTIMIZATION ANNEALERS

  • Domain-wall variable encoding uses only single-body fields and ferromagnetic couplings, which can be implemented more strongly than antiferromagnetic couplings in flux-qubit hardware.For relatively small discrete sets, specialized annealers may therefore retain much of the problem-setting dynamic range available to a binary machine.Source: §V · p. 6
  • A transverse-field driver can access invalid higher-energy states, so their energy separation must be large enough to keep them out of reach.A driver that preserves the feasible subspace would require a significant advance in available mixer terms.Source: §V · p. 6
  • An application-specific annealer could reduce embedding overhead when a high-value family of problems has similar or identical structure.The passage suggests that reducing or eliminating this overhead could substantially improve performance relative to current non-specialized annealers.Source: §V · p. 6
  • Domain-wall transitions under a transverse-field driver do not pass through invalid states, unlike one-hot transitions, whose effective coupling decreases as constraint penalties increase.The absence of this encoding-strength versus coupling-strength trade-off may simplify specialized hardware design.Source: §V · pp. 6–7

VI. EMBEDDING/COMPILATION

Domain-wall and one-hot encodings differ in qubit count, within-variable connectivity, and the interactions needed to represent functions between variables. Because hardware connectivity drives embedding overhead, these structural differences matter; the examples are limited to quantum-annealing embeddings.

VI. EMBEDDING/COMPILATION

  • Domain-wall encoding uses one fewer qubit per discrete variable and linear within-variable connectivity, whereas one-hot encoding requires full connectivity.The qubit saving can matter for small discrete variables; for Z3 variables, it reduces the qubit count by one third.Source: §VI · p. 7
  • Both encodings can implement arbitrary two-variable functions with two-body interactions, but the required inter-variable couplers and their structure differ by interaction.Depending on the interaction, either encoding may require more inter-variable interactions.Source: §VI · p. 7
  • Within-variable qubits are always one edge apart in one-hot encoding, while their distance in domain-wall encoding can reach n − 1.The passage defines edge distance as the minimum number of graph edges between two vertices.Source: §VI · p. 7
  • Minor embedding reduces available qubits and can produce broken variables; on quasi-planar geometries, representable fully connected graphs scale only as the square root of the qubit count.Parity-based encodings retain the same square-root scaling in such geometries.Source: §VI · p. 7
  • Because gate-model hardware structure remains unclear and embedding strategies are less developed, the study restricts specific examples to quantum-annealing embeddings.On gate-model devices, swaps can add circuit depth, a concern for near-term shallow circuits.Source: §VI · p. 7

VII. EXAMPLES

Across the examined problem structures, domain-wall encoding offers at least a small advantage over one-hot encoding, though the advantage varies substantially with problem structure. Scheduling and three-colouring illustrate that the relative embedding efficiency can differ by problem, while the qubit saving can change the overall preference.

VII. EXAMPLES

  • Across all examined problem families, domain-wall encoding yields at least a small advantage over one-hot encoding, with the advantage highly dependent on problem structure.The study compares embeddings on D-Wave chimera and Pegasus graphs.Source: §VII · p. 7
  • For synthetic scheduling, the embedding-efficiency advantage between domain-wall and one-hot encodings is comparable to that between chimera and Pegasus graphs.Both graph families are included in the numerical embedding study.Source: §VII · p. 7
  • For maximum three-colouring, domain-wall embedding is slightly less efficient, but its one-fewer-qubit requirement per variable makes it the preferred strategy overall.The result is presented as an example of how encoding and embedding trade-offs depend on the problem.Source: §VII · p. 8

A. Unstructured Interactions

Domain-wall encoding uses a subgraph of one-hot hardware for unstructured interactions. For graph coloring, it uses fewer qubits and is no larger to embed on average in the tested cases, with the advantage depending on problem structure.

A. Unstructured Interactions

  • For unstructured interactions among three Z4 variables, domain wall needs 9 qubits and 36 interactions, versus one hot's 12 qubits and 76 interactions.The domain-wall interaction graph is a subgraph of the one-hot graph, so every interaction it needs is also present in one hot.Source: A. Unstructured Interactions · p. 8, Figure 2 · p. 8

B. Graph Coloring

  • The domain-wall encoding requires fewer qubits in all cases; when r > rc, it uses fewer qubits but more interactions than one-hot, with rc(3) = 2 and rc(4) = 4/3.The domain-wall structure is easier to implement and therefore preferable at large sizes.Source: B. Graph Coloring · p. 9
  • Domain-wall embeddings are no larger on average across tested colorings, with the gap growing markedly for n-color problems (Figure 5).The study tests three-color and n-color problems on Chimera and Pegasus graphs.Source: Figure 5 · p. 10, B. Graph Coloring · p. 10
  • For n-color problems, domain wall has a layered structure with minimum edge distance |i − j| between layers, a structure absent from one hot.The reported embedding results associate this structure with more efficient embedding for n-color problems.Source: B. Graph Coloring · pp. 9–10

C. Scheduling

The scheduling encoding represents conflicts between events with domain-wall interactions. Its interaction count grows with the number of potential conflict times, and its average embedding size is smaller than one hot's in the tested schedule problems.

C. Scheduling

  • Domain-wall encodings require an average smaller host graph than one hot for the tested schedule-conflict problems (Figure 7).The figure reports results on Chimera and Pegasus for problems with different numbers of events.Source: Figure 7 · p. 11, C. Scheduling · p. 11
  • In the domain-wall schedule encoding, edge distance grows linearly with the allowed time range, whereas one hot's maximum edge distance remains two.The figure depicts conflicts at a single time and their accumulation across allowed start times.Source: C. Scheduling · pp. 10–11
  • For q potential conflict times, domain wall requires at most 4q binary interactions, independent of event durations, while one hot's interaction count grows with event duration.Each potential conflict can use four pairwise interactions, or fewer when a variable is at an extremal value.Source: C. Scheduling · p. 11

D. Analysis

Embedding gains from domain-wall encoding depend strongly on problem structure, while Pegasus consistently reduces embedding overhead across the studied structures. The section also describes numerical benchmark setup and a domain-wall construction analogous to k-hot encoding.

D. Analysis

  • For three-colour problems, domain-wall embedding is slightly less efficient than one-hot, whereas max n-colouring and scheduling show more efficient domain-wall embedding at large sizes.For three-colour problems, the observed advantage instead comes from domain-wall encoding requiring fewer variables.Source: D. Analysis · p. 11
  • Across the studied structures, Pegasus yields a consistent large embedding-overhead advantage, while the domain-wall advantage ranges from a slight disadvantage on three-colour problems to a scheduling gain comparable to Pegasus over Chimera.Figure 9 compares relative embedding ratios across the problem and hardware-graph settings; its points average 10 instances.Source: D. Analysis · p. 12, Figure 9 · p. 12

VIII. NUMERICAL METHODS

  • The benchmarks use general-purpose embedding software and randomly generated colouring and scheduling instances, which represent problem structure rather than provably hard problems.The colouring graphs use edge probabilities 0.5 for three colours and 0.75 for n colours; scheduling conflicts are sampled with probability 0.75.Source: §VIII · p. 12

IX. EXTENSION: DOMAIN WALL ANALOGUE OF k-HOT ENCODINGS

  • Unlike one-hot encoding, domain-wall chains cannot produce k-hot behaviour merely by changing single-body strengths; multiple chains can instead enforce distinct values through colouring constraints.The proposed analogue may require more logical qubits than k-hot, and its embedding-efficiency tradeoff for real problems is left for future study.Source: §IX · pp. 12–13
  • A domain-wall k-hot analogue can enforce ordered, distinct values across neighbouring chains using local interactions and an added penalty term.The described construction penalizes adjacent variables when their values fail the required ordering.Source: §IX · p. 13

X. DISCUSSION AND CONCLUSIONS

The paper presents domain-wall encoding for discrete variables and their interactions, then compares its embedding with one-hot on Chimera and Pegasus graphs. The reported embedding gains vary by problem, and the discussion identifies possible mechanisms, hardware implications, and open work.

X. DISCUSSION AND CONCLUSIONS

  • For every examined problem type, domain-wall encoding embeds more efficiently than one-hot, with improvement depending strongly on problem type and sometimes comparable to Pegasus-over-Chimera gains.For synthetic scheduling problems embedded in Pegasus, the physical-to-logical-bit ratio gains are comparable between domain-wall versus one-hot and Pegasus versus Chimera.Source: §X · p. 13
  • The paper encodes discrete variables and arbitrary classical two-variable interactions with two-body Ising terms, and describes two-body QAOA mixers that preserve the logically valid space.The mixer construction is noted as previously demonstrated for one-hot encoding.Source: §X · p. 13
  • The authors suggest that domain-wall variables can spread farther than one-hot variables, potentially fitting problem structure such as noninteracting events scheduled far apart.The study uses general-purpose heuristic embedding software; specialized software or application-specific hardware could reduce embedding overhead, potentially eliminating it.Source: §X · p. 13
  • The paper identifies efficient decomposition of problems that do not fit a quantum annealer's hardware graph as an open research direction.The discussion points to prior work on decomposition strategies [62–64] and their broader importance.Source: §X · p. 13
  • Domain-wall structure may support discrete or mixed binary/integer problems that map to hardware with no embedding overhead, which could simplify interpretation of quantum-annealing experiments.The paper also identifies reverse annealing as a possible way to trade off optimality and robustness in future work [68].Source: §X · p. 13

Appendix 1: Explantion of performance metrics given in table II

The appendix explains metrics for comparing binary, one-hot, and domain-wall encodings, then introduces shared definitions used to specify example-problem Hamiltonians.

# qubits

  • Logical qubit count measures the qubits required to represent the problem, excluding binary-encoding auxiliaries used to implement constraints.Source: # qubits · p. 14

# couplers for encoding

  • Encoding coupler count measures two-body couplers that constrain qubits to the logically valid subspace; non-power-of-two binary domains may require higher-order constraints and auxiliary qubits.Source: # couplers for encoding · p. 14

intra-variable connectivity

  • Intra-variable connectivity is fully connected for one-hot constraints and linear for domain-wall constraints; binary connectivity depends on the number of values.For non-power-of-two binary domains, excluding configurations can require complicated higher-order coupling structures.Source: intra-variable connectivity · p. 14

maximum order needed to penalize single values

  • The maximum coupling order for penalizing one logical value is one for one-hot and domain-wall encodings, but may involve all binary qubits.Some binary penalties, such as a penalty linear in the encoded value, need only single-body terms.Source: maximum order needed to penalize… · p. 14

maximum order needed for two variable interactions

  • The maximum coupling order for arbitrary two-variable interactions is two for one-hot and domain-wall encodings, while binary encoding may require coupling all qubits in both variables.Specific binary interactions can need lower order; a quadratic interaction needs only one- and two-body terms.Source: maximum order needed for two variable… · p. 14

maximum de between qubits in interacting variables

  • Maximum edge distance measures the shortest interaction-graph path between qubits encoding different interacting variables, as a rough measure of how spread out an encoding can be.For binary encoding, the distance is case-dependent because implementing interactions may require auxiliary qubits.Source: maximum de between qubits in… · p. 14

Appendix 2: Hamiltonians for examples

A. Unstructured Interactions

The appendix specifies Hamiltonian formulations for unstructured interactions, graph colouring, and scheduling, with each formulation grounded in the corresponding problem representation.

A. Unstructured Interactions

B. Graph colouring

  • The graph-colouring formulation represents edges with a strictly upper-triangular matrix and constrains adjacent vertices to take different colours.The formulation considers K vertices and N available colours.Source: B. Graph colouring · p. 15

C. Scheduling

  • The scheduling formulation represents m events with time windows, durations, and pairwise conflicts, and defines whether two events overlap in time.The conflict matrix records which event pairs cannot occur simultaneously.Source: C. Scheduling · p. 15
Loading 1903.05068v4…