Pith. sign in

REVIEW 4 major objections 3 minor 1 cited by

Adaptive Quantum Computers: decoding and state preparation

T0 review · 4 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adaptive quantum computers—quantum circuits that interact with a classical computer mid-computation—can provably beat standard constant-depth circuits at recovering messages from corrupted Hadamard codes, and can prepare common quantum…

desk verdict A useful paper with a real quantum decoding construction and a classical hardness proof that currently rests on unverified black-box applicability. read the letter →

arxiv 2509.08718 v1 pith:ZPZ7OAQY submitted 2025-09-10 quant-ph

Niels M. P. Neumann This is my paper · ORCID
classification quant-ph MSC 81P6868Q1268Q1594B35
keywords adaptivequantumcomputinglistdecodingHadamardcodeReed–Mullerconstant-depthcircuitsadvantageGHZstatequerycomplexity
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that a quantum computer that hands intermediate results to a classical computer—an "adaptive quantum computer"—is strictly more powerful than a standard computer for a concrete, practical task: recovering messages from heavily corrupted digital data. It proves that constant-depth quantum circuits with parity gates can list-decode a corrupted Hadamard code with success probability $\Omega(\varepsilon^2)$, while no constant-depth classical circuit with parity gates can decode any code with constant success probability. The proof splits the problem into a structured case and a random-like case using a new analytic rank for polynomial maps. The same adaptive approach yields a query-efficient algorithm for decoding degree-2 Reed–Muller codes, and a second formal model (LAQCC) produces constant-depth protocols for preparing uniform superpositions, GHZ, W, and Dicke states, with hardware-backed error analysis showing higher success probabilities than non-adaptive alternatives.

What carries the argument

The load-bearing objects are four. First, the analytic rank of polynomial maps—a measure of how far a map is from being uniform modulo lower-degree maps—splits the classical-hardness proof into a pseudorandom high-rank case (controlled by a random-restriction theorem) and a structured low-rank case (controlled by a bias-implies-low-rank theorem). Second, the quantum Fourier-sampling subroutine, a generalization of Bernstein–Vazirani, samples the Fourier spectrum of multiplicative derivatives and drives both the Hadamard decoder and the quadratic decoder. Third, an algorithmic Balog–Szemerédi–Gowers theorem converts spectral concentration into a small-doubling set and then into an approximating matrix $M$, which yields the quadratic correlation. Fourth, in Part II the LAQCC model lets a constant-depth quantum circuit call unbounded-fan-in classical parity and OR computations mid-circuit, enabling a quantum fanout gate and constant-depth GHZ-state correction; this is the mechanism that gives constant-depth decoding and the improved state-preparation circuits.

What would settle it

Simulate the depth-65 circuit for $n=16$ with noiseless gates and confirm that the distribution of the sum of measurement outcomes matches $(1 - 2d(c,H(x))/n)^2$ from Theorem 4.2.1; if it does not, the GHZ/fanout construction has an accounting error. Alternatively, attempt to construct an NC$^0[\oplus]$ circuit family that decodes a corrupted Hadamard code with constant success probability at any fixed $\delta < 1/2$, which would directly refute Theorem 3.1.1.

Watch

Extended reading notes

Core claim

The central discovery is a separation: for every constant error parameter $\delta \in (0,1/2)$, list decoding the Hadamard code separates QNC$^0[\oplus]$ from NC$^0[\oplus]$, and for error rates $1/2-\varepsilon$ with $\varepsilon$ between $\log n/\sqrt{n}$ and $1/(\log n)^{\omega(1)}$, the List-Hadamard problem separates QNC$^0[\oplus]$ from AC$^0[\oplus]$. The quantum side is a depth-65 circuit family that implements the Hadamard-decode non-local game: players share GHZ states, apply phase flips controlled by corrupted coordinates, Hadamard-transform, and measure, so the sum of the answers equals the original message with probability $\Omega(\varepsilon^2)$. The classical side proves that no NC$^0[\oplus]$ circuit can decode any code with constant success probability, because such circuits compute constant-degree polynomials and polynomial maps of constant degree cannot invert encoding-plus-noise. For quadratic Reed–Muller codes, a quantum algorithm makes $O_\varepsilon(n\log n)$ queries and returns a degree-2 polynomial $g$ with $\delta(f,g) \le 1/2 - \eta$ whenever the input $f$ is within $1/2 - \varepsilon$ of some degree-2 codeword, improving the classical query complexity by a factor $n$.

Load-bearing premise

The classical hardness side rests on two imported theorems about polynomial rank—bias implies low rank, and random restrictions preserving high rank—and if either fails at the exact degree, characteristic, and noise parameters used, the separation between quantum and classical constant-depth decoding collapses.

Editorial extensions

If this is right

  • For any constant error parameter $\delta < 1/2$, there is a concrete decoding problem—recovering messages from corrupted Hadamard codewords—where adaptive constant-depth quantum circuits provably outperform constant-depth classical circuits with parity gates.
  • The same decoding circuit yields a QNC$^0[\oplus]$ circuit for Majority, extending the known power of constant-depth quantum circuits to threshold functions without unbounded-fan-in majority gates.
  • For corrupted degree-2 Reed–Muller codewords, the query algorithm improves on the classical approach by a factor $n$, giving a near-quadratic quantum speedup for learning quadratic polynomials in the presence of noise.
  • The LAQCC model shows that uniform superpositions, GHZ, W, and Dicke states can all be prepared in constant depth when classical parity operations are available mid-circuit, lowering circuit depth for algorithms that use these states as subroutines.
  • The error analysis indicates that these adaptive routines can have higher success probabilities than non-adaptive constant-depth alternatives under realistic noise, which matters for near-term devices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial: the decoding separation is likely not unique to the Hadamard code; the same GHZ-fanout machinery should decode any code whose codewords are affine functions over $\mathbb{F}_2$, and the analytic-rank template should adapt whenever an algorithmic inverse theorem for the appropriate Gowers norm is available at the required field size.
  • Editorial: a near-term experimental check would be to compile the depth-65 Hadamard decoder for $n=16$–$32$ qubits, count the classical parity operations the LAQCC model exposes, and measure whether the success probability tracks $(1 - 2d(c,H(x))/n)^2$ as the noiseless model predicts.
  • Editorial: the factor-$n$ query reduction suggests that other higher-order Fourier-analytic algorithms—for instance the cubic Goldreich–Levin algorithm—might gain the same speedup by swapping classical Fourier estimation for quantum Fourier sampling, an idea the paper names as future work.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The manuscript formalizes a model of adaptive quantum computers (called LAQCC) and studies two tasks. Part I treats decoding: Chapter 3 proves that no NC0[⊕] circuit (equivalently, no constant-degree polynomial map) can decode an arbitrary error-correcting code under biased noise with constant success probability; Chapter 4 gives a constant-depth QNC0[⊕] circuit that decodes a corrupted Hadamard codeword with probability Ω(ε²) and uses this to claim separations between QNC0[⊕] and NC0[⊕]/AC0[⊕]; Chapter 5 gives a quantum algorithm that, given a function close to a degree-2 Reed-Muller codeword, finds a correlated quadratic phase with O_ε(n log n) queries. Part II introduces the LAQCC model, gives constant-depth state-preparation routines for uniform, GHZ, W, and Dicke states, and compares them to non-adaptive alternatives both analytically and on quantum hardware.

Significance. If the central theorems are fully established, the paper provides a natural decoding problem with a provable separation between constant-depth quantum circuits with classical feedback and standard constant-depth circuits, complementing earlier artificial separations such as 2D Hidden Linear Function and Relaxed Parity Halving. The classical hardness theorem is attractively general, applying to every error-correcting code, and the Ω(ε²) decoding probability in Theorem 4.2.1 is derived cleanly from the Fourier amplitude of the corrupted Hadamard word. The Chapter 5 algorithm extends a substantial line of work on algorithmic higher-order Fourier analysis, and the query lower bounds in Section 5.7 are clearly stated. However, several load-bearing steps are either imported theorems whose hypotheses are not verified, a reduction that is explicitly only sketched, or a lemma without proof; these gaps need to be closed before the advertised separations can be considered proven.

major comments (4)
  1. [Section 4.5, Theorem 4.5.3 (first clause)] The first clause of Theorem 4.5.3 asserts that list decoding the Hadamard code with any constant error parameter δ < 1/2 separates QNC0[⊕] from NC0[⊕]. This is not established by the results proved in the paper. Theorem 3.1.1 bounds the success probability of an NC0[⊕] circuit whose output is the message x, i.e. a map F_2^n → F_2^k; it says nothing about a circuit that outputs a list L(y) of length up to n/4 containing x. Corollary 4.6.2 gives hardness for the list-Hadamard problem only in the regime ε(n) ≤ 1/(log n)^{ω(1)}, which excludes constant ε = 1/2 − δ. Unless a separate lower bound for list decoding at constant δ is supplied, the theorem should be restated as a separation for exact decoding, which is what Theorems 3.1.1 and 4.1.1 actually demonstrate.
  2. [Section 4.6.2] The conversion of the quantum list-decoding circuit into a Majority circuit is explicitly presented as a sketch. In particular, the text does not specify how a probabilistic quantum subroutine C whose output is a classical list obtained by measurement can be used inside an oracle QNC0[⊕] circuit while preserving the claimed success probabilities 1 − O(n^{-1/4}) and 1 − O(n^{-1/8}); it also does not account for the total depth and size of the classical post-processing, including the equality checks between m and every list element and the OR reductions. Since the second part of Theorem 4.5.3 depends on this reduction, the claimed separation from AC0[⊕] is not proven as written. Please provide a complete construction or explicitly mark that separation as conditional on a completed version of this argument.
  3. [Section 3.4, Lemma 3.4.2 and Theorem 3.4.1] The random-restriction theorem is imported from [BC24] and applied to the analytic rank of Definition 3.3.2, with the assertion that the four properties in Lemma 3.3.4 make the theorem applicable. The manuscript does not state the hypotheses of [BC24, Theorem 1.8] nor verify that the present arank_d satisfies them in the regimes used later, in particular over F_2 and with the maximum over lower-degree polynomial maps in the definition. This is load-bearing: the pseudorandom case of Theorem 3.1.2, and hence the conventional-hardness side of the central separation, depends quantitatively on the constants κ(d,σ) and R(d,σ,ε). Please reproduce the imported theorem and its verification, or give a direct proof of the biased-equidistribution lemma.
  4. [Section 5.1.1, Lemma 5.1.6] Lemma 5.1.6 asserts that a Fourier-mass lower bound on the multiplicative derivatives of f implies that the graph A = {(h, φ(h))} has large additive energy. No proof is given, and this lemma is used later in Section 5.3 (via Proposition 5.3.1) and in Section 5.6 to establish Lemma 5.1.2 and hence Theorem 5.1.1. Since the energy lower bound is the starting point for the Balog-Szemerédi-Gowers step, the proof of the main theorem of Chapter 5 is incomplete as written. Please add a proof or a precise reference that contains the proof.
minor comments (3)
  1. [Equation (5.16)] The upper bound |⟨B3⟩| ≤ exp(−poly(1/γ)) |H0| has the wrong sign: the exponential factor should be exp(poly(1/γ)), since a set size cannot be bounded above by an exponentially small multiple of |H0|. The same notation appears in Equation (5.17) and should be corrected for consistency.
  2. [Theorem 4.5.3] The notation ε(n) ≤ 1/(log n)^{ω(1)} is ambiguous; it should be clarified, for example as 'ε(n) ≤ (log n)^{-C} for every fixed constant C', so that the intended regime in the theorem is unambiguous.
  3. [Section 4.4, Lemma 4.4.1] The size accounting for a conditional phase gate as O(k 2^k) = O(n log n) is unclear. If the Takahashi-Tani OR gate on k inputs has size O(k), the total circuit size would be O(n log n), not O(n² log n); if it uses the 2^k subset parities from the Fourier expansion, the stated size needs justification. Please reconcile the count or state which size bound is actually needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central separation and state-preparation claims are derived from explicit Fourier/Chernoff analyses and external, non-self-cited theorems; the only self-reference is a transparent thesis attribution.

full rationale

I walked the derivation chain of the main results. Theorem 3.1.2 does not assume its own conclusion: it defines the analytic rank (Definition 3.3.2), then proves the impossibility result by a two-case dichotomy in Section 3.5. In the pseudorandom case, high analytic rank triggers the biased-equidistribution lemma, whose proof invokes the external random-restriction theorem of Briët and Castro-Silva (Theorem 3.4.1). In the structured case, low analytic rank lets the paper decompose the map into lower-degree maps using the external bias-implies-low-rank theorem of Kaufman and Lovett (Theorem 3.3.1), after which the proof finishes by ordinary induction on the degree. This is a standard structure-versus-randomness induction, not a circular reduction: the lower-degree maps are genuinely different objects, and the target probability bound is never inserted as an input. The imported theorems come from outside the paper and are not replaced by the paper's own claims. A possible mismatch between the paper's analytic rank and the rank notion in [BC24] would be a correctness or hypothesis-matching risk, not a self-referential reduction. The quantum decoding result in Chapter 4 is also derived from first principles: the winning probability in Equation (4.3) is computed directly from Fourier magnitudes of the corrupted Hadamard codeword, and the Omega(epsilon^2) bound follows from Chernoff and the union bound. No parameter is fitted to a subset of data and then renamed a prediction. In Chapter 5, the query algorithm and lower bounds are built on the Fourier-sampling lemma (Lemma 1.7.5), the Balog-Szemerédi-Gowers theorem, and standard information-theoretic bounds (Fano's inequality and Holevo's theorem); again the target correlation is not used as an input. The only self-reference in the manuscript is the front-matter note: 'This document is the online and update version of the author’s PhD thesis. The original version is found online at [Neu25].' That is a document-level attribution and is not load-bearing for any mathematical claim. No self-definitional, fitted-input-called-prediction, ansatz-smuggling, or renaming pattern is present. The paper is not fully self-contained because it relies heavily on external black-box theorems, but that is an evidence/completeness consideration, not circularity. I therefore find no circular step and assign score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central results are derived from stated theorems and no empirical constants are fitted. The main burden is the set of external additive-combinatorics and inverse-theorem results used as black boxes, plus the LAQCC convention that classical parity and fanout operations are unit-cost in constant depth.

assumptions (6)
  • standard math NC0[+] circuits of depth d are equivalent to polynomial maps of total degree at most d over F_2.
    Section 3.1 converts the circuit lower bound into a theorem about polynomial maps.
  • standard math Kaufman and Lovett's bias-implies-low-rank theorem for polynomials (Theorem 3.3.1 of [KL08]).
    Used in the structured case of the proof of Theorem 3.1.2 to decompose low-rank polynomial maps.
  • standard math Briet and Castro-Silva's random-restriction theorem for analytic rank (Theorem 3.4.1 of [BC24]).
    Used to show high-rank polynomial maps remain high-rank under biased random restrictions, the key step in the pseudorandom case.
  • standard math Green-Tao and Samorodnitsky inverse theorems for the Gowers U^3 norm (Lemmas 5.1.3 and 5.1.4).
    Convert large derivative Fourier mass into a quadratic phase correlation in the quadratic decoding algorithm.
  • standard math Balog-Szemeredi-Gowers and Freiman-Ruzsa theorems (Theorems 5.1.7 and 5.1.8).
    Used to promote weak linearity of the sampled map to exact linearity on a large subspace in Chapter 5.
  • domain assumption The LAQCC model counts intermediate classical parity computations as unit-depth operations within the circuit class.
    This accounting is what makes the adaptive state-preparation circuits shallower than non-adaptive circuits; the assumption is part of the model definition in Part II.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Quantum Computers: decoding and state preparation." pith.science (2026). https://pith.science/paper/ZPZ7OAQY

@misc{pith2026250908718,
  author       = {Pith},
  title        = {Pith review of: Adaptive Quantum Computers: decoding and state preparation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZPZ7OAQY}},
  note         = {Machine review of arXiv:2509.08718}
}
read the original abstract

Interacting with a standard computer can enhance the capabilities of current quantum computers already today, particularly by offloading certain computations to the standard computer. Quantum computers that interact with standard computers to perform computations are called adaptive quantum computers. This work formalizes a model that describes these adaptive quantum computers. As quantum computers are still under development, this work focuses on computations that terminate after a fixed number of steps, as that makes their implementation likely easier in practice. First, we show that adaptive quantum computers are more powerful than standard computers with respect to the practical problem of retrieving information from corrupted digital data. Standard computers struggle to retrieve such information within a fixed number of computation steps. The proof uses a structure-versus-randomness approach that splits the problem in a structured and a random-like component. The potential of adaptive quantum computations follows from a specific example where information is retrieved from corrupted data. Additionally, adaptive quantum computers can even improve standard computations for this problem that are not constrained by a fixed number of computation steps. Next, we show how adaptive quantum computations can improve non-adaptive quantum computations when preparing specific quantum states. We present efficient adaptive quantum algorithms to prepare the uniform superposition state, the GHZ state, the W-state and the Dicke state. These states are often used in other quantum algorithms, so having efficient routines for preparing them also enhances the efficiency of other algorithms. This work concludes by comparing these adaptive quantum computations with non-adaptive ones, analyzing their performance both theoretically and through quantum hardware implementations.

Figures

Figures reproduced from arXiv: 2509.08718 by the authors.

Figure 1.1
Figure 1.1. An example of a circuit. The n inputs are shown at the bottom and every square box represents an elementary operation. Time flows from the bottom to the top. The dotted box denotes a layer and the number of numbers equals the depth of the circuit. operations in that layer and the width of the circuit as a whole equals the maximum width across all layers. The depth of a circuit is defined as the minimum number of lay… view at source ↗
Figure 1.2
Figure 1.2. An example quantum circuit. Each line represents a qubit. The shown quantum circuit prepares the quantum state √ 1 2 (|00⟩ + |11⟩). Quantum circuits are often depicted with time running from left to right, as shown in [PITH_FULL_IMAGE:figures/full_fig_p011_1_2.png] view at source ↗
Figure 1.3
Figure 1.3. Overview of different quantum computers with the available number of qubits over the years. between the quantum and conventional algorithm becomes clear in the number of queries to the database. Conventional algorithms can only check a single item at a time. Quantum algorithms can query the database “in superposition”, which roughly means checking the entire database at once. The successive queries are needed for co… view at source ↗
Figures from the paper (21 more)
Figure 1.4
Figure 1.4. Figure 1.4: A quantum circuit that implements the quantum Fourier transform. The gates Rk correspond to RZ(π/2 k )-gate. analysis to show that any sufficiently large subset of positive integers contains a triple (a, b, c) such that the difference between two successive numbers i…
Figure 4.1
Figure 4.1. Figure 4.1: The quantum circuit to generate a 3-qubit GHZ state. First, we prepare a poor man’s cat state √ 1 2 (|z⟩ + |z¯⟩) with each z ∈ F 3 2 equally likely to be found. The parity gates compute a prefix sum on the measurement results d1 and d2 and determine if a qubit has to…
Figure 4.2
Figure 4.2. Figure 4.2: Implementation of a quantum fanout gate with one control qubit |ϕ⟩ and two target qubits |x1⟩ and |x2⟩. Only single- and two-qubit gates and conventional parity gates are used. The bottom three qubits are in the GHZ3 state. The dotted lines denote time steps and whic…
Figure 7.1
Figure 7.1. Figure 7.1: shows a LAQCC-circuit that implements a Clifford-ladder circuit. Every two-qubit unitary is parallelized using gate teleportation. Using the Clifford commutation relations, the Pauli correction terms are pushed to the end of the computation. The caps and cups denote …
Figure 7.2
Figure 7.2. Figure 7.2: Graphical representation of transforming a LAQCC∗ -circuit for gener￾ating |ψ⟩ into a PostQPoly-circuit. 7.7 Reflections and outlook This chapter introduced the LAQCC-model that alternates between conventional and quantum operations. The LAQCC-model generalizes alrea…
Figure 8.1
Figure 8.1. Figure 8.1: shows the steps of the Uncompress operation graphically for n = 4. We explicitly leave out auxiliary qubits in the shown circuits. H H 1 2෍𝑖=0 3 𝑖 00 ⊗3 0000 1 2෍𝑖=0 3 𝑖𝑖𝑖𝑖 0000 Equal0 Equal1 Equal2 Equal3 1 2෍𝑖=0 3 𝑖𝑖𝑖𝑖 𝑒𝑖 1 2෍𝑖=0 3 𝑖 00 ⊗3 𝑒𝑖 [PITH_FULL_IMAGE:figu…
Figure 8.2
Figure 8.2. Figure 8.2: shows the steps of the Compress operation graphically for n = 4. We again omit the auxiliary qubits from the shown circuits. H H H H 1 4෍𝑖,𝑗=0 3 −1 ⟨𝑖,𝑗⟩ 𝑗 00 ⊗3 𝑒𝑖 1 4෍𝑖,𝑗=0 3 −1 ⟨𝑖,𝑗⟩ 𝑗 ⊗4 𝑒𝑖 1 4෍𝑖,𝑗=0 3 𝑗 ⊗4 𝑒𝑖 1 2෍𝑖=0 3 00 ⊗4 𝑒𝑖 Z Z Z Z 1 4෍𝑖,𝑗=0 3 𝑗 00 ⊗3 𝑒𝑖 [P…
Figure 8.3
Figure 8.3. Figure 8.3: Circuit for the Filling operation for n = 4 and k = 2. Shown is a grid of 24 qubits: 16 light gray index qubits and 8 dark gray system qubits. Each grid represents a single step. where [PITH_FULL_IMAGE:figures/full_fig_p097_8_3.png]
Figure 8.4
Figure 8.4. Figure 8.4: shows the circuit to compute the Hamming weight of the system register qubits for n = 4. Note that we need only three computations, as system qubit i uses the Hamming weight of the first i − 1 system qubits. We omitted the index registers, and instead show the auxili…
Figure 8.5
Figure 8.5. Figure 8.5: Circuit to clean index register j. The black dots represent qubits in the system register and the light gray dots the index register and its copies. The gray squares denote auxiliary registers of log k qubits each. Each grid represents a single time step. The proof o…
Figure 9.1
Figure 9.1. Figure 9.1: Identity for the controlled-U gate. Using the success probabilities from [PITH_FULL_IMAGE:figures/full_fig_p107_9_1.png]
Figure 9.2
Figure 9.2. Figure 9.2: shows a quantum circuit to prepare the GHZ state for n = 8 using an all-to-all connec￾tivity. In every subsequent time step, twice as many qubits can be targeted. |0⟩ H |0⟩ |0⟩ |0⟩ |0⟩ |0⟩ |0⟩ |0⟩ t=0 t=1 t=2 t=3 t=4 [PITH_FULL_IMAGE:figures/full_fig_p108_9_2.png]
Figure 9.3
Figure 9.3. Figure 9.3: shows a quantum circuit to prepare the GHZ state for n = 6 using a linear nearest￾neighbor connectivity. The key difference from the previous approach is that qubits can now only interact with their direct neighbors, and hence at most two CNOT-gates per layer can be …
Figure 9.4
Figure 9.4. Figure 9.4: GHZ state preparation using a LAQCC circuit. The LAQCC-circuit uses 2n − 1 qubits and the circuit depth remains constant, even with growing n. The success probability at time t = 4 is given by p n s p n−1 is p 2(n−1) d p 2 idp n−1 m p n im. A prefix sum computation o…
Figure 9.5
Figure 9.5. Figure 9.5: Measurement results for preparing a GHZ state on few qubits on the IBM Brisbane device using the LAQCC-approach and the standard approach. Horizontally, the different measurement results are shown and the height of the bars shows how often that measurement result is …
Figure 9.6
Figure 9.6. Figure 9.6: Measurements results for preparing a GHZ state on n = 20 and n = 25 qubits on the IBM Brisbane device using the LAQCC-approach and the standard approach. Horizontally, the different measured Hamming weights are shown and the height of the bars shows how often that Ha…
Figure 9.7
Figure 9.7. Figure 9.7: Measurement results for preparing a GHZ state on n = 30, n = 40, and n = 55 qubits on the IBM Brisbane device using the LAQCC-approach and the standard approach. Horizontally, the different measured Hamming weights are shown and the height of the bars shows how often…
Figure 9.8
Figure 9.8. Figure 9.8: Implementation of a quantum fanout gate with the GHZ state prepa￾ration expanded. The time steps indicate which gates can be applied in parallel. We can extend the circuit shown in [PITH_FULL_IMAGE:figures/full_fig_p119_9_8.png]
Figure 9.9
Figure 9.9. Figure 9.9: LAQCC-circuit that prepares the state [PITH_FULL_IMAGE:figures/full_fig_p120_9_9.png]
Figure 9.10
Figure 9.10. Figure 9.10: Exact circuit for preparing the W-state for n = 4. Every gate parametrized by 1/n denotes a controlled-RY -gate with argument θ = −2 arccos p 1/n. |0⟩ 1/4 |0⟩ C B A |0⟩ C ′ B′ A′ |0⟩ [PITH_FULL_IMAGE:figures/full_fig_p123_9_10.png]
Figure 9.11
Figure 9.11. Figure 9.11: Exact decomposed circuit for preparing the W-state for n = 4, where every controlled RY -gate is replaced by single-qubit gates and CNOT-gates. Each CNOT-gate will then correctly set one additional qubit, until we have the desired W-state. The idea behind this circu…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. State preparation via measurement and feedback: pushing relations, state structures, and non-invertible symmetries

    quant-ph 2026-08 conditional novelty 8.0 of 10

    Finite-depth measurement-feedback preparation of 1D matrix product states is classified by pushable virtual-bond defects and their pushing relations, yielding explicit circuits and links to non-invertible symmetries.

Reference graph

Works this paper leans on

43 extracted references · 6 canonical work pages · cited by 1 Pith paper

  1. [1]

    The Computational Complexity of Linear Optics

    [AA13] S. Aaronson and A. Arkhipov. “The Computational Complexity of Linear Optics”. In:Theory of Computing9 (2013), pp. 143–252.doi:10.4086/toc.2013.v009a004. [AA15] S. Aaronson and A. Ambainis. “Forrelation: A Problem that Optimally Separates Quantum from Classical Computing”. In:Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computi...

    arXiv 2013

  2. [2]

    Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?

    1957, pp. 94–104. [EPR35] A. Einstein, B. Podolsky, and N. Rosen. “Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?” In:Phys. Rev.47 (May 1935), pp. 777– 780.doi:10.1103/PhysRev.47.777. [ER59] P. Erd¨ os and A. R´ enyi. “On random graphs I”. In:Publ. math. debrecen6 (1959), p. 18.doi:10.5486%2FPMD.1959.6.3-4.12. [Eur24] EuroH...

    doi:10.1103/physrev.47.777 1959

  3. [5]

    Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

    arXiv:2408.06289 [quant-ph]. [Aha+07] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev. “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation”. In:SIAM Journal on Computing37 (2007), pp. 166–194.doi:10.1137/S0097539705447323. 127 BIBLIOGRAPHY 128 [Ajt83] M. Ajtai. “Σ 1 1-formulae on finite structures”. In:Annals ...

    arXiv 2007

  4. [9]

    Deterministic Preparation of Dicke States

    arXiv:2410 . 21811 [quant-ph]. [BE19] A. B¨ artschi and S. Eidenbenz. “Deterministic Preparation of Dicke States”. In:Fun- damentals of Computation Theory. Springer International Publishing, 2019, pp. 126– 139.isbn: 978-3-030-25027-0. [BE22] A. B¨ artschi and S. Eidenbenz. “Short-Depth Circuits for Dicke State Preparation”. In:2022 IEEE International Conf...

    arXiv 2019

  5. [12]

    Quantum advantage with noisy shallow circuits

    arXiv:2301.00995 [quant-ph]. [Bra+20] S. Bravyi, D. Gosset, R. K¨ onig, and M. Tomamichel. “Quantum advantage with noisy shallow circuits”. In:Nat. Phys.16 (2020). Preliminary version in FOCS’19, pp. 1040–1045.issn: 1745-2473, 1745-2481.doi:10.1038/s41567-020-0948-z. [Bra+22] S. Brandhofer, D. Braun, V. Dehn, G. Hellstern, M. H¨ uls, Y. Ji, I. Polian, A. ...

    arXiv 2020

  6. [14]

    Generalized Clifford groups and simulation of associated quantum circuits

    arXiv:2408.06967 [quant-ph]. [CJL08] S. Clark, R. Jozsa, and N. Linden. “Generalized Clifford groups and simulation of associated quantum circuits”. In:Quantum Info. Comput.8 (Jan. 2008), pp. 106–126. issn: 1533-7146. [Cla+69] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt. “Proposed Experiment to Test Local Hidden-Variable Theories”. In:Phys. Rev...

    arXiv 2013

  7. [15]

    Validating quantum computers using randomized model circuits

    arXiv:quant-ph/0201067 [quant-ph]. [Cro+19] A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta. “Validating quantum computers using randomized model circuits”. In:Phys. Rev. A100 (Sept. 2019), p. 032328.doi:10.1103/PhysRevA.100.032328. [CSV21] M. Coudron, J. Stark, and T. Vidick. “Trading Locality for Time: Certifiable Ran- domness fr...

    arXiv 2021

  8. [18]

    Experimentally ac- cessible nonseparability criteria for multipartite-entanglement-structure detection

    Gauthier-Villars, 1888.doi: 10.1017/CBO9780511693229. [Gar+23] G. Garc´ ıa-P´ erez, O. Kerppo, M. A. C. Rossi, and S. Maniscalco. “Experimentally ac- cessible nonseparability criteria for multipartite-entanglement-structure detection”. In:Phys. Rev. Res.5 (Mar. 2023), p. 013226.doi:10.1103/PhysRevResearch.5. 013226. [GC99] D. Gottesman and I. L. Chuang. “...

    arXiv 1999

Show all 43 references
  1. [24]

    Grover algorithm with zero theoretical failure rate

    arXiv:2406.16142 [quant-ph]. [Lon01] G. L. Long. “Grover algorithm with zero theoretical failure rate”. In:Phys. Rev. A 64 (July 2001), p. 022307.doi:10.1103/PhysRevA.64.022307. [Lov19] S. Lovett. “The analytic rank of tensors and its applications”. In:Discrete Anal. (2019), P...

    2019

  2. [30]

    A variational eigenvalue solver on a photonic quantum processor

    arXiv:1910. 09534 [quant-ph]. [Per+14] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru- Guzik, and J. L. O’Brien. “A variational eigenvalue solver on a photonic quantum processor”. In:Nature Communications5 (July 2014), p. 4213.issn: 2041-172...

    2021

  3. [31]

    Demonstration of Fidelity Improvement Using Dynamical Decoupling with Superconducting Qubits

    Ed. by J. Mikyˇ ska, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. Sloot. Cham: Springer Nature Switzerland, 2023, pp. 18–33.isbn: 978-3-031-36030-5. doi:10.1007/978-3-031-36030-5_2. [Pok+18] B. Pokharel, N. Anand, B. Fortman, and D. A. Lidar....

    1954

  4. [36]

    New bounds in Balog-Szemer´ edi-Gowers theorem

    2024, pp. 941–951.doi:10.1109/QCE60285.2024.00113. [Sch14] T. Schoen. “New bounds in Balog-Szemer´ edi-Gowers theorem”. In:Combinatorica 35 (Oct. 2014), pp. 695–701.doi:10.1007/s00493-014-3077-4. [Sha48] C. E. Shannon. “A mathematical theory of communication”. In:The Bell Syst...

    1948

  5. [37]

    On the Power of Quantum Computation

    arXiv:2404.02280 [quant-ph]. [Sim97] D. R. Simon. “On the Power of Quantum Computation”. In:SIAM Journal on Com- puting26 (1997), pp. 1474–1483.doi:10.1137/S0097539796298637. [Siu+93] K.-Y. Siu, J. Bruck, T. Kailath, and T. Hofmeister. “Depth efficient neural networks for divi...

    1997 arXiv

  6. [39]

    Multipartite entanglement and high-precision metrology

    2023, pp. 1–12.doi:10.1109/QCE57702.2023.00009. [T´ ot12] G. T´ oth. “Multipartite entanglement and high-precision metrology”. In:Phys. Rev. A85 (Feb. 2012), p. 022322.doi:10.1103/PhysRevA.85.022322. [Tre04] L. Trevisan.Some Applications of Coding Theory in Computational Complexity

    2023

  7. [40]

    Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

    arXiv:cs/0409044 [cs.CC]. [TT13] Y. Takahashi and S. Tani. “Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits”. In:2013 IEEE Conference on Computational Complexity. 2013, pp. 168–178.doi:10.1109/CCC.2013.25. [Tur37] A. M. Turing. “On Computable Numbers, with a...

    1937 arXiv

  8. [42]

    Efficient compression of quantum information

    [PB10] M. Plesch and V. Buˇ zek. “Efficient compression of quantum information”. In:Phys. Rev. A81 (Mar. 2010), p. 032317.doi:10.1103/PhysRevA.81.032317. [PCZ22] F. Pan, K. Chen, and P. Zhang. “Solving the Sampling Problem of the Sycamore Quantum Circuits”. In:Phys. Rev. Lett....

    2010 doi

  9. [43]

    A Fast Quantum Mechanical Algorithm for Database Search

    2007, pp. 69–102. [Gro96] L. K. Grover. “A Fast Quantum Mechanical Algorithm for Database Search”. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC ’96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–21...

    2009

  10. [44]

    [Wac+21] A

    doi:10.1007/978-3-662-03927-4. [Wac+21] A. Wack, H. Paik, A. Javadi-Abhari, P. Jurcevic, I. Faro, J. M. Gambetta, and B. R. Johnson.Quality, Speed, and Scale: three key attributes to measure the performance of near-term quantum computers

    doi

  11. [45]

    A Multilevel Algorithm for Large Uncon- strained Binary Quadratic Optimization

    arXiv:2110.14108 [quant-ph]. [Wan+12a] Y. Wang, Z. L¨ u, F. Glover, and J.-K. Hao. “A Multilevel Algorithm for Large Uncon- strained Binary Quadratic Optimization”. In:Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems. Springer...

    2012 arXiv

  12. [95]

    Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords

    [Yam16] T. Yamakami. “Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords”. In:Baltic J. Modern Computing 4 (2016), pp. 753–788.doi:10.22364/bjmc.2016.4.4.12. [Yao77] A. C.-C. Yao. “Probabilistic computations: Toward a u...

    2016 doi arXiv

  13. [104]

    Polynomial Codes Over Certain Finite Fields

    [RS60] I. S. Reed and G. Solomon. “Polynomial Codes Over Certain Finite Fields”. In: Journal of the Society for Industrial and Applied Mathematics8 (1960), pp. 300–304. doi:10.1137/0108018. [RSA78] R. L. Rivest, A. Shamir, and L. Adleman. “A Method for Obtaining Digital Signat...

    1960

  14. [126]

    Coherent Josephson Qubit Suitable for Scalable Quantum Inte- grated Circuits

    Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019, 12:1–12:11.isbn: 978-3-95977-100-9.doi:10.4230/LIPIcs.STACS.2019.12. [Bar+13] R. Barends et al. “Coherent Josephson Qubit Suitable for Scala...

    2019 doi

  15. [137]

    Hybrid Quantum-Classical Approach to Quantum Optimal Control

    Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019, 21:1–21:20.isbn: 978-3- 95977-116-0.doi:10.4230/LIPIcs.CCC.2019.21. [Li+17] J. Li, X. Yang, X. Peng, and C.-P. Sun. “Hybrid Quantum-Classical A...

    2019 doi

  16. [215]

    Low-Degree Tests at Large Distances

    Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 112:1–112:4.isbn: 978-3-95977-217-4.doi:10.4230/LIPIcs.ITCS. 2022.112. [Sam07] A. Samorodnitsky. “Low-Degree Tests at Large Distances”. In:P...

    2009

  17. [443]

    Eval- uating the Q-score of Quantum Annealers

    [Sch+22] W. v. d. Schoot, D. Leermakers, R. Wezeman, N. Neumann, and F. Phillipson. “Eval- uating the Q-score of Quantum Annealers”. In:2022 IEEE International Conference on Quantum Software (QSW). 2022, pp. 9–16.doi:10.1109/QSW55613.2022.00017. [Sch+23] W. van der Schoot, R. ...

    2023

  18. [1678]

    Gate Set Tomography

    [Nie+21] E. Nielsen, J. K. Gamble, K. Rudinger, T. Scholten, K. Young, and R. Blume-Kohout. “Gate Set Tomography”. In:Quantum5 (Oct. 2021), p. 557.issn: 2521-327X.doi: 10.22331/q-2021-10-05-557. [NM14] Y. Nakata and M. Murao. “Diagonal quantum circuits: Their computational pow...

    2021 doi

  19. [1985]

    Probability Inequalities for Sums of Bounded Random Variables

    [Hoe63] W. Hoeffding. “Probability Inequalities for Sums of Bounded Random Variables”. In: Journal of the American Statistical Association58 (1963), pp. 13–30.doi:10.1080/ 01621459.1963.10500830. [Hou+09] A. A. Houck, J. Koch, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf....

    1963

  20. [1998]

    A new proof of Szemer´ edi’s theorem

    arXiv: quant-ph/9807006 [quant-ph]. [Gow+25] W. Gowers, B. Green, F. Manners, and T. Tao.On a conjecture of Marton. Mar. 2025.doi:10.4007/annals.2025.201.2.5. [Gow01] W. Gowers. “A new proof of Szemer´ edi’s theorem”. In:GAFA, Geom. funct. anal. 11 (Aug. 2001), pp. 465–588.doi...

    2025 arXiv

  21. [1999]

    Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations

    arXiv:quant- ph/9903046 [quant-ph]. [MR18] D. Maslov and M. Roetteler. “Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations”. In:IEEE Transactions on Information Theory 64 (2018), pp. 4729–4738.doi:10.1109/TIT.2018.2825602. [MTS24] R. Mao, ...

    2018

  22. [2002]

    Quantum Computation with Linear Optics

    Ed. by H. Alt and A. Ferreira. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 323–334.isbn: 978-3-540-45841-8.doi:10 . 1007/3-540-45841-7_26. [AC98] C. Adami and N. J. Cerf. “Quantum Computation with Linear Optics”. In:Selected Papers from the First NASA Internation...

    2002

  23. [2004]

    Cubic Goldreich-Levin

    arXiv:quant-ph/0403090 [quant-ph]. [KLT23] D. Kim, A. Li, and J. Tidor. “Cubic Goldreich-Levin”. In:Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for In- dustrial and Applied Mathematics, Jan. 2023, pp. 4846–4892.doi:10 . 1137 / 1 . 9...

    2010 arXiv

  24. [2009]

    On Certain Sets of Integers

    Springer Berlin Heidelberg, 2009, pp. 663–674.doi:10.1007/ 978-3-642-03816-7_56. [Rot53] K. F. Roth. “On Certain Sets of Integers”. In:Journal of the London Mathematical Society28 (1953), pp. 104–109.doi:https://doi.org/10.1112/jlms/s1-28.1

    1953 doi

  25. [2014]

    Transmission of information: A statistical theory of communications

    arXiv:1411.4028 [quant-ph]. BIBLIOGRAPHY 132 [FH61] R. M. Fano and D. Hawkins. “Transmission of information: A statistical theory of communications”. In:Am. J. Phys.29 (1961), pp. 793–794.doi:10.1119/1.1937609. [Fou88] J. B. J. Fourier.Th´ eorie analytique de la chaleur. Vol

    1961 arXiv

  26. [2017]

    A divide-and-conquer algorithm for quantum state preparation

    2017, pp. 836–845.doi: 10.23919/DATE.2017.7927104. [Ara+21] I. F. Araujo, D. K. Park, F. Petruccione, and A. J. da Silva. “A divide-and-conquer algorithm for quantum state preparation”. In:Sci Rep11 (2021), p. 6329.doi:10. 1038/s41598-021-85474-1. [Aru+19] F. Arute et al. “Qua...

    2021

  27. [2018]

    Long-Range Entanglement from Measuring Symmetry-Protected Topological Phases

    arXiv:1810.11563 [hep-th]. [Tan+24] N. Tantivasadakarn, R. Thorngren, A. Vishwanath, and R. Verresen. “Long-Range Entanglement from Measuring Symmetry-Protected Topological Phases”. In:Phys. Rev. X14 (June 2024), p. 021040.doi:10.1103/PhysRevX.14.021040. [TBG17] K. Temme, S. B...

    2024 arXiv

  28. [2019]

    Logical Reversibility of Computation

    Phoenix, AZ, USA: Association for Computing Machinery, 2019, pp. 515–526.isbn: 9781450367059.doi:10.1145/3313276.3316404. [Ben73] C. H. Bennett. “Logical Reversibility of Computation”. In:IBM Journal of Research and Development17 (1973), pp. 525–532.doi:10.1147/rd.176.0525. [B...

    1973

  29. [2020]

    Fault-tolerant quantum computation with constant error

    arXiv:2009.07450 [quant-ph]. [AB09] S. Arora and B. Barak.Computational complexity. A modern approach. Cam- bridge University Press, Cambridge, 2009.isbn: 978-0-521-42426-4.doi:10.1017/ CBO9780511804090. [AB97] D. Aharonov and M. Ben-Or. “Fault-tolerant quantum computation wit...

    2009 arXiv

  30. [2021]

    A statistical theorem of set addition

    Virtual, Italy: Association for Computing Machinery, 2021, pp. 1303–1316.isbn: 9781450380539.doi:10 . 1145 / 3406325 . 3451040. [BS94] A. Balog and E. Szemer´ edi. “A statistical theorem of set addition”. In:Combinatorica 14 (Sept. 1994), pp. 263–268.issn: 1439-6912.doi:10.100...

    1997

  31. [2022]

    XACC: a system-level software infrastructure for heterogeneous quantum–classical computing

    arXiv:2103.17193 [cs.ET]. [McC+20] A. J. McCaskey, D. I. Lyakh, E. F. Dumitrescu, S. S. Powers, and T. S. Humble. “XACC: a system-level software infrastructure for heterogeneous quantum–classical computing”. In:Quantum Science and Technology5 (Feb. 2020), p. 024002.doi: 10.108...

    2020 arXiv

  32. [2023]

    [BP23] A

    arXiv:2312.05060 [quant-ph]. [BP23] A. Bene Watts and N. Parham.Unconditional Quantum Advantage for Sampling with Shallow Circuits

    arXiv

  33. [2024]

    A Quantum Goldreich-Levin Theorem with Cryptographic Applications

    arXiv:2410.22220 [quant-ph]. [AC02] M. Adcock and R. Cleve. “A Quantum Goldreich-Levin Theorem with Cryptographic Applications”. In:STACS

    arXiv

  34. [2025]

    Blind quantum computation

    arXiv:2509.02338 [math.CO]. [AS06] P. Arrighi and L. Salvail. “Blind quantum computation”. In:International Journal of Quantum Information4 (Oct. 2006), pp. 883–898.doi:10.1142/s0219749906002171. [Bab82] C. Babbage. “On the Theoretical Principles of the Machinery for Calculati...

    2006 arXiv

  35. [2417]

    Dynamical suppression of decoherence in two-state quantum systems

    [VL98] L. Viola and S. Lloyd. “Dynamical suppression of decoherence in two-state quantum systems”. In:Phys. Rev. A58 (Oct. 1998), pp. 2733–2744.doi:10.1103/PhysRevA. 58.2733. [VMS04] J. J. Vartiainen, M. M¨ ott¨ onen, and M. M. Salomaa. “Efficient Decomposition of Quantum Gate...

    1998 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.