PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum state preparation for weighted d-DNNF

Steef Hegeman, Joon Hyung Lee, Alfons Laarman

arXiv:2610.02094v1quant-phcs.DS

TL;DR

Quantum state preparation is hard in general and can cancel a quantum algorithm’s advantage. This paper gives an efficient circuit-generation method for states represented by weighted d-DNNF, with linear-time description up to complex arithmetic.

  • Problem

    Preparing a quantum state from its classical description is hard in general and can even cancel a quantum algorithm’s advantage.

    Source: §1 · p. 1

  • Method

    The algorithm creates a superposition over partial certificates, increasing depth until it reaches a superposition over all certificates.

    Source: §9.1 · p. 11

  • Results

    A weighted d-DNNF D yields a quantum circuit of size O(|D|) and depth O(depth(D) log |D|), whose description is computed in O(|D|) time up to complex arithmetic.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The result supplies an efficient state-preparation route for weighted d-DNNF inputs, addressing a generally hard step that can cancel quantum advantage.

    Source: §1 · p. 1

    Converting weighted FBDD to weighted d-DNNF increases size by a constant factor, so direct use of may be more ancilla-efficient for a small FBDD with no much smaller d-DNNF.

    Source: §9.1 · pp. 10–11

Abstract

from arXiv · show

The quantum state preparation problem is to, given a description of a quantum state, efficiently generate a quantum circuit computing the state. We show that for quantum states described by weighted d-DNNF (deterministic, decomposable pseudo-Boolean circuits) a quantum circuit computing the state can be obtained in linear time up to complex arithmetic.

1. Introduction

Quantum state preparation can be hard in general and may cancel a quantum algorithm’s advantage. The paper shows that weighted d-DNNF descriptions support efficient preparation, with a circuit description computable in linear time up to complex arithmetic.

1. Introduction

  • Quantum state preparation can be hard in general and can cancel out a quantum algorithm’s advantage.Source: §1 · p. 1
  • For weighted d-DNNF D, the preparation circuit has size O(|D|), depth O(depth(D) log |D|), and a description computable classically in O(|D|) time up to complex arithmetic.The stated RAM model treats complex-register operations +, ×, ÷, absolute value, and square root as constant time.Source: §1 · p. 1
  • Weighted d-DNNF is exponentially more succinct than weighted FBDD for representing quantum states, as prepared in.Source: §1 · p. 1

2. Definitions

The definitions establish weighted d-DNNF circuits, their certificates, and the quantum-state vectors and circuit dimensions used in the paper.

2. Definitions

  • A pseudo-Boolean circuit over C uses ×-gates, weighted +-gates, and Boolean-variable literals, with assignments evaluated by replacing each literal with its Boolean value.Source: §2.1 · p. 1

2.1. Weighted d-DNNF.

  • Weighted d-DNNF circuits are pseudo-Boolean circuits with deterministic OR-gates and decomposable AND-gates: distinct OR children have pairwise-zero weighted products, while distinct AND children share no variables.A weighted 2-d-DNNF has gates with fan-in and fan-out at most two and no unary AND-gates.Source: §2.1 · pp. 1–2

2.2. Certificates.

  • A certificate is a smallest nonzero subcircuit containing the output gate; determinism and decomposability ensure each assignment has at most one certificate, which is a tree.For a nonzero assignment, the circuit value equals the product of the edge weights in its certificate.Source: §2.2 · pp. 2–3

2.3. Quantum state preparation.

  • The paper defines S1 by summing assignment amplitudes and S2 by grouping certificate values over assignments; for smooth d-DNNF, S1(D) = S2(D).The stated gate set includes X, CX, and single-qubit U(p, q), with additional controlled gates used initially for readability.Source: §2.3 · p. 3

2.4. Gate notation.

  • Classical circuit size counts gates plus wires, and its depth is the longest path from the output gate to a gate.Source: §2.5 · p. 3

2.5. Circuit dimensions.

  • Quantum circuit width counts targeted qubits, while depth is the smallest possible depth under a gate scheduling that respects conflicts on shared qubits.Source: §2.5 · p. 3

3. Main results

The paper constructs linear-size state-preparation circuits for normalized weighted 2-d-DNNF and extends the result to weighted d-DNNF. The circuits have depth proportional to the representation depth, with a logarithmic factor for the general d-DNNF result.

3. Main results

  • Normalized weighted 2-d-DNNF states have circuits with O(|D|) gates, depth O(depth(D)), and 2|int(D)| − 2 ancillas, describable in linear time up to complex arithmetic.Theorem 4 also gives constant parallel time with poly(|D|) processors for the circuit description.Source: §3 · p. 3
  • A weighted 2-d-DNNF whose S2(D) is a state can be normalized without changing the state, while an S1(D) state can be reweighted as an S2(D′) state.Both transformations modify only edge weights and take linear time up to complex arithmetic.Source: §3 · p. 4
  • Weighted 2-d-DNNF states represented as S1(D) or S2(D) also have circuits with O(|D|) gates, depth O(depth(D)), and 2|int(D)| − 2 ancillas.Their circuit descriptions can be computed in linear time up to complex arithmetic.Source: §3 · pp. 3–4
  • For weighted d-DNNF representing an S1(D) or S2(D) state, the stated circuit has O(|D|) gates, width O(|D|), and depth O(depth(D) log |D|).Its description takes linear time up to complex arithmetic.Source: §3 · pp. 3–4
  • The circuits can be made to use only gates from {X, CX} ∪ SU(2).This gate-set result is proved in Appendix A.Source: §3 · p. 4

4. Construction overview

The overview builds a superposition over weighted certificates and assignments, then uses nonzero-gate information to reset the certificate registers. The circuit is organized into certificate propagation, nonzero, and reset layers.

4. Construction overview

  • Starting with the root gate marked and variable qubits in |+⟩, certificate propagation expands a superposition over partial certificates according to gate structure and OR-gate weights.AND-gates include all children, while weighted OR-gates split amplitude between exactly one selected child.Source: §4 · p. 4
  • The circuit has certificate propagation, nonzero, and reset layers, with the nonzero layer followed by reset operations and an inversion of the nonzero computation.The Figure 3 caption marks the boundaries between the three layers.Source: §4 · pp. 4–5, Figure 3 · p. 5
  • The nonzero layer computes which gates evaluate to nonzero for each assignment and stores those indicators in n_g qubits.The indicators then control resetting the certificate-gate qubits.Source: §4 · p. 4
  • Although several controlled-H gates may act on a variable qubit, at most one fires in any basis state of nonzero amplitude because each partial certificate contains a variable at most once.The reset layer clears n_g by inverting the nonzero layer.Source: §4 · p. 5

5. The state preparation algorithm

For normalized weighted 2-d-DNNF, the construction uses gate ancillas, nonzero ancillas, and variable qubits to implement three circuit layers. Subcircuits follow each gate’s type and are scheduled according to the circuit’s dependencies.

5. The state preparation algorithm

  • The circuit initializes the root certificate qubit to |1⟩, other internal-gate qubits and nonzero ancillas to |0⟩, and each variable qubit to |+⟩.It allocates c_g for internal gates, n_g for internal gates other than the output, and v_x for variables.Source: §5 · p. 6
  • The certificate layer uncomputes D top-to-bottom to mark certificates, the nonzero layer evaluates D bottom-to-top, and the reset layer clears c_g and then n_g.The layer descriptions specify the overall roles of the three circuit stages.Source: §5 · p. 6
  • Certificate subcircuits P_g propagate through AND-gates and use weighted controlled operations at OR-gates, with literal handling specified by F_a.For OR-gates with at most two inputs, the construction orders internal gates and literals before applying the controlled operations.Source: §5 · p. 6
  • Nonzero subcircuits N_g compute gate nonzeroness from child indicators, while reset subcircuits R_g clear certificate ancillas using those indicators.The construction schedules P_g top-to-bottom and N_g and R_g bottom-to-top; gates on disjoint qubits can be applied in parallel.Source: §5 · p. 6

6. Correctness

Correctness follows by tracking how the circuit expands partial certificates, computes gate nonzeroness, and resets its ancillas. The resulting circuit prepares S2(D) for normalized weighted 2-d-DNNF when S2(D) is a state.

6. Correctness

  • After the first layer, the circuit’s state is a superposition over partial certificates, whose extensions under each gate follow the certificate rules and OR-gate weights.At a weighted binary OR, the two extensions receive amplitudes weighted by w0 and w1.Source: §6 · p. 7
  • The second layer records which gates are nonzero under each assignment in the n_g registers.The proof identifies these registers with the Boolean evaluation of the gates on that assignment.Source: §6 · p. 7
  • The third layer resets the c_g and n_g ancillas while leaving the variable qubits untouched.Determinism ensures the unique selected OR-child in a certificate is the child marked nonzero, allowing the reset operations to clear the certificate registers.Source: §6 · pp. 7–8
  • For normalized weighted 2-d-DNNF D with S2(D) a state, Q(D) computes S2(D).This conclusion combines the certificate-layer, nonzero-layer, and reset-layer results.Source: §6 · p. 8

7. Complexity

The circuit Q(D) has linear size and is generated in linear time up to complex arithmetic; its depth scales with the depth of D. The section bounds its width and explains how its gates are scheduled.

7. Complexity

  • Lemma 13 states that Q(D) consists of O(|D|) gates, has width |var(D)| + 2|I| − 1 < 2|D|, and has depth O(depth(D)).Source: §7 · p. 8
  • The gates at each level can be scheduled in constant depth, yielding depth O(depth(D)) on gate set G.The argument uses bounded-degree conflict graphs, which can be colored with at most 7 colors; a more careful count gives depth at most 11 depth(D)+O(1).Source: §7 · p. 8
  • A description of Q(D) can be computed sequentially in O(|D|) time up to complex arithmetic.The subcircuits have constant size and can also be described in constant parallel time using poly(|D|) processors.Source: §7 · p. 8
  • The scheduling of Lemma 13 can be computed in linear time, and qubit cr can be eliminated from Q(D).The scheduling is not part of the circuit description; cr remains |1⟩ until reset and can then be removed.Source: §7 · pp. 8–9

8. Preparing S1(D)

The section extends state preparation to S1(D) and to non-normalized weighted 2-d-DNNF by reweighting and normalization. These transformations can be computed in linear time up to complex arithmetic.

8. Preparing S1(D)

  • The section establishes preparation of S1(D) and S2(D) for any weighted 2-d-DNNF by reweighting and normalization.The stated result covers S2 states for normalized circuits and reweights circuits whose S1(D) is a state.Source: §8 · p. 9
  • For S1(D) ≠ 0, a linear-time-up-to-complex-arithmetic reweighting produces D′ with S2(D′) ∝ S1(D).The construction adjusts certificate values in proportion to 2^−|var(τ)|/2, using recursively defined K_g factors.Source: §8 · p. 9
  • For S2(D) ≠ 0, a normalized reweighting D′ preserves the represented direction: S2(D′) = S2(D)/|S2(D)|.The reweighting is computable in linear time up to complex arithmetic by computing the gate-state norms using a recurrence.Source: §8 · p. 10
  • A weighted 2-d-DNNF D with S1(D) a state can be reweighted into normalized D′ with S1(D) = S2(D′) in linear time up to complex arithmetic.This combines the reweighting and normalization results.Source: §8 · p. 10

9. Related work

The related-work discussion compares exact preparation from weighted d-DNNF with weighted FBDD and other knowledge-compilation approaches, then contrasts it with approximate Grover–Rudolph preparation.

9.1. Weighted FBDD.

  • The method asymptotically subsumes weighted-FBDD preparation and is strictly more succinct, since some states have polynomial-size d-DNNF but require exponential-size weighted FBDD.A linear-time conversion from weighted FBDD to weighted d-DNNF gives circuit size and width O(|F|) and depth O(min(|F|, depth(F) log |F|)).Source: §9.1 · p. 10
  • When a state has a small weighted FBDD and no much smaller weighted d-DNNF, direct weighted-FBDD preparation may be more ancilla-efficient.The discussed FBDD method uses an ancilla for each node and prepares a superposition over paths; this method uses unique certificates and additional wires to uncompute certificate ancillas.Source: §9.1 · pp. 10–11

9. Related work

  • The overview and comparisons in Tanaka et al. [24, Table 1] also apply to this method because it asymptotically subsumes theirs.The authors say they focus on additional comparisons, including a stricter comparison with Grover–Rudolph / Kaye–Mosca preparation.Source: §9.2 · p. 11

9.2. Other related work.

  • Comparisons across state-preparation methods require accounting for input-language succinctness and whether preparation is exact or approximate.This method and the weighted-FBDD method are exact; many other methods target approximation within an error bound.Source: §9.2 · p. 11

9.2.1. Knowledge-compilation-based state preparation.

  • d-DNNF, SDNNF, and non-deterministic FBDD are pairwise incomparable; current tractable approaches for the corresponding MPS and TTN representations are, to the authors’ knowledge, approximate or assume low bond dimension.Weighted SDNNF correspond to TTN, while weighted non-deterministic FBDD correspond to MPS.Source: §9.2.1 · p. 11

9.2.2. Grover–Rudolph preparation.

  • Grover–Rudolph preparation can be implemented efficiently from weighted d-DNNF, but yields an approximation with size poly(m, |D|) and depth O(|var(D)| polylog(m, |D|)).It computes approximate amplitudes and phases through modifications of the arithmetic circuit underlying D; the paper contrasts its exact approach as having sharper size and width bounds and a matching depth bound.Source: §9.2.2 · pp. 11–12

Appendix A. Reducing the gate set

The appendix shows how to reduce the circuit’s gate set to {X, CX} ∪ SU(2). It replaces controlled gates using constant-size constructions, with basis-state-specific substitutes for doubly controlled gates.

Appendix A. Reducing the gate set

  • The gate set {X, CX} ∪ SU(2) suffices for the circuit.The reduction replaces the other gates used in Q(D).Source: Appendix A · p. 13
  • CU(p, q) can be implemented with two CX and three SU(2) gates, while H and CH are composed from X or CX with controlled-U gates.The stated decompositions use U(2^−1/2, 2^−1/2).Source: Appendix A · p. 13
  • CCX and CCH occurrences are replaced by constant-size subcircuits that act appropriately on the basis states occurring in Q(D).The chosen controlled-U parameters depend on whether the gates fire on |0⟩, |1⟩, or |+⟩.Source: Appendix A · p. 13

Appendix B. Succinctness of weighted knowledge compilation languages for quantum state representation

Appendix B notes that weighted succinctness is less established than unweighted succinctness and proves an exponential succinctness gap between weighted d-DNNF and weighted FBDD. Appendix C gives a bounded constant-removal transformation.

Appendix B. Succinctness of weighted knowledge compilation languages for quantum state representation

  • Redirecting zero-weight edges and removing weights would turn a small weighted FBDD for ψ_f into a small FBDD for f, contradicting the chosen family [4].Source: Appendix B · pp. 13–14
  • Weighted FBDD is exponentially less succinct than weighted d-DNNF for representing quantum states.Source: Appendix B · p. 14
  • The argument extends to cited deterministic-representation separations, but weighted nondeterministic representations can introduce cancellation, so it generally does not apply there.Source: Appendix B · p. 14

Appendix C. Weighted d-DNNF with constants

  • A nonconstant weighted d-DNNF with constant gates can be made constant-free in linear time up to complex arithmetic, with size at most 2|D| and depth at most twice the original.Source: Appendix C · p. 14
Loading 2610.02094v1…