BPBO: Blindness-Preserving Brickwork Optimization by Certified Region Resynthesis

Doyoung Chung; Juyoung Kim; Youngkyung Lee

arxiv: 2606.29962 · v1 · pith:DTS2KT4Ynew · submitted 2026-06-29 · 🪐 quant-ph · cs.CR

BPBO: Blindness-Preserving Brickwork Optimization by Certified Region Resynthesis

Youngkyung Lee , Juyoung Kim , Doyoung Chung This is my paper

Pith reviewed 2026-06-30 06:32 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR

keywords universal blind quantum computationUBQCbrickwork patternspattern resynthesisblindness preservationmeasurement-based quantum computationGrover search

0 comments

The pith

BPBO performs certified local resynthesis on blind quantum computation brickwork patterns while preserving blindness.

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

The paper develops BPBO to optimize BFK09-compatible brickwork patterns in universal blind quantum computation by detecting one-, two-, and three-wire regions and replacing them with smaller equivalents. Each candidate replacement is accepted only after explicit checks confirm that branch frames, output frames, and blinding behavior remain unchanged. The resulting patterns stay standard brickwork graphs and run on an existing logical-qubit-recycled UBQC stack. A sympathetic reader would care because the method reduces pattern size for concrete algorithms while relying only on compatibility with existing blindness and verification guarantees rather than new security proofs.

Core claim

BPBO detects regions, supplies semantic floors or executable witnesses, and accepts a replacement only after branch-frame, output-frame, and blinding-behavior checks; the security statement is a compatibility result that preserves UBQC blindness at the declared dimensions and remains compatible with inherited verification guarantees under explicit test-round conditions, without a new trap-soundness theorem, as shown by reductions such as Grover-3 from 3 x 725 to 3 x 98 while preserving expected marked-state statistics.

What carries the argument

The resynthesis procedure that applies branch-frame, output-frame, and blinding-behavior checks after each candidate replacement to certify that the change does not alter overall blindness or verification properties.

Load-bearing premise

The branch-frame, output-frame, and blinding-behavior checks performed after each candidate replacement are sufficient to guarantee that the resynthesized region does not alter the overall blindness or verification properties of the full pattern.

What would settle it

Running the same client computation on both the original and an optimized pattern and observing a statistically significant difference in output distribution or a detectable leak of computation information would falsify the blindness-preservation claim.

Figures

Figures reproduced from arXiv: 2606.29962 by Doyoung Chung, Juyoung Kim, Youngkyung Lee.

**Figure 1.** Figure 1: FIG. 1. Blindness-preserving brickwork optimization (BPBO) and qubit-recycled execution workflow. (a) BPBO lowers a [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Figure 2: FIG. 2. L3 phase-gadget obstruction for two clean macro [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3. Grover-3 materialization cost at the three stages of [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4. Decoded output distribution of the optimized Grover [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

read the original abstract

Universal blind quantum computation (UBQC) hides a client's computation by using a computation-independent BFK09 brickwork graph and encoding the computation in measurement angles, which limits the use of graph-changing optimizations. We study blindness-preserving brickwork optimization (BPBO): certified local resynthesis of BFK09-compatible brickwork patterns below the blinding layer. BPBO detects one-, two-, and three-wire regions; for each candidate region it either proves a semantic floor or supplies an executable witness, and it accepts a replacement only after its branch-frame, output-frame, and blinding behavior have been checked. The optimized outputs remain standard brickwork patterns and are evaluated with a logical qubit-recycled UBQC execution stack that runs arbitrary-length patterns using n x 2 active logical qubits. The layer evidence includes a one-wire H-count floor, a two-wire CNOT-cost floor, a three-wire parity-ledger floor, a clean three-cell CCZ witness whose optimality claim is scoped to the CNOT+T phase-gadget family, and an endpoint-target three-cell CCX/Toffoli application witness; the fixed middle-target CCX case is retained as a four-cell fallback. The security statement is a compatibility result: BPBO preserves UBQC blindness at the declared optimized dimensions and remains compatible with inherited verification guarantees under explicit test-round conditions, without introducing a new trap-soundness theorem. On Bell/CX, Grover-2, endpoint-Toffoli, and Grover-3 evaluation cases, BPBO demonstrates certified local reductions; in the largest case, Grover-3, the materialized pattern is reduced from 3 x 725 to 3 x 98 while preserving the expected marked-state statistics up to sampling noise.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

BPBO shows concrete local reductions on UBQC brickwork patterns via certified resynthesis, but the blindness claim rests on checks whose global sufficiency is not formally established.

read the letter

The main takeaway is that this paper describes a method to shrink BFK09 brickwork patterns for blind quantum computation by replacing small regions after running frame and blinding checks, with reported cuts like Grover-3 from 3x725 to 3x98 while keeping the expected output statistics.

What is actually new is the BPBO pipeline: region detection for one- to three-wire cases, either a semantic-floor proof or an executable witness, followed by branch-frame, output-frame, and blinding-behavior checks before accepting the replacement. The outputs remain standard brickwork, and they evaluate them on a logical-qubit-recycled stack that handles arbitrary-length patterns with only n x 2 active qubits. The examples cover Bell/CX, Grover-2, endpoint-Toffoli, and Grover-3, and the optimality claims are scoped narrowly, such as the three-cell CCZ witness limited to the CNOT+T phase-gadget family.

The practical side is handled reasonably: they keep fallbacks where needed and account for sampling noise in the runs. The security statement is explicitly a compatibility result that inherits UBQC blindness without a new trap-soundness theorem.

The soft spot is exactly the one flagged in the stress-test note. Acceptance of each resynthesis depends on the three post-replacement checks being enough to ensure the full pattern still satisfies the standard blindness definition (measurement outcomes independent of client angles). The abstract describes the checks but does not include a lemma or reduction showing that local satisfaction of those conditions implies the global property when the region sits inside an arbitrary surrounding pattern. That gap is load-bearing for the security claim.

This paper is for specialists working on resource reduction inside universal blind quantum computation. A reader already familiar with BFK09 and brickwork implementations would get the most from the concrete cases and the check-based method. It has enough targeted substance and reproducible examples to deserve a serious referee, though the blindness argument needs tightening.

Referee Report

1 major / 2 minor

Summary. The paper introduces blindness-preserving brickwork optimization (BPBO) for universal blind quantum computation (UBQC) based on BFK09 brickwork patterns. It performs certified local resynthesis on one-, two-, and three-wire regions by proving semantic floors or supplying executable witnesses, accepting replacements only after branch-frame, output-frame, and blinding-behavior checks. The security claim is a compatibility result that inherits UBQC blindness without a new trap-soundness theorem. The work supplies layer evidence (one-wire H-count floor, two-wire CNOT-cost floor, three-wire parity-ledger floor, clean three-cell CCZ witness scoped to CNOT+T phase gadgets, endpoint-target CCX/Toffoli witness) and evaluates on Bell/CX, Grover-2, endpoint-Toffoli, and Grover-3 cases, reporting a reduction from 3×725 to 3×98 in the largest instance while preserving marked-state statistics up to sampling noise. A logical qubit-recycled UBQC execution stack is used to handle arbitrary-length patterns.

Significance. If the three post-replacement checks are formally shown to suffice for global blindness preservation, the result would enable concrete resource reductions in blind quantum computation while remaining compatible with existing verification. Explicit witnesses for optimality floors in specific gate families and the demonstrated size reductions (particularly the Grover-3 case) are concrete strengths; the compatibility framing avoids overclaiming new security theorems. The approach is scoped to BFK09-compatible brickwork and does not alter the overall pattern class.

major comments (1)

[Security statement] Security statement (abstract and corresponding section): the manuscript states that BPBO is a compatibility result that preserves UBQC blindness via the branch-frame, output-frame, and blinding-behavior checks, but supplies no lemma or reduction showing that satisfaction of these three local conditions implies the standard BFK09 blindness definition (i.e., that the joint distribution of measurement outcomes on the full pattern remains independent of the client's secret angles) when the resynthesized region is embedded in an arbitrary surrounding brickwork. This is load-bearing for the central security claim.

minor comments (2)

The definitions of 'semantic floor' and 'executable witness' are used repeatedly but would benefit from an explicit introductory paragraph or table that distinguishes the two notions and lists which regions receive which treatment.
Table or figure summarizing the four evaluation cases (Bell/CX, Grover-2, endpoint-Toffoli, Grover-3) with before/after dimensions and the specific witness or floor applied would improve readability of the results section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting this central point on the security statement. We address the comment below.

read point-by-point responses

Referee: [Security statement] Security statement (abstract and corresponding section): the manuscript states that BPBO is a compatibility result that preserves UBQC blindness via the branch-frame, output-frame, and blinding-behavior checks, but supplies no lemma or reduction showing that satisfaction of these three local conditions implies the standard BFK09 blindness definition (i.e., that the joint distribution of measurement outcomes on the full pattern remains independent of the client's secret angles) when the resynthesized region is embedded in an arbitrary surrounding brickwork. This is load-bearing for the central security claim.

Authors: We agree that the manuscript does not supply an explicit lemma or reduction proving that the three local checks imply preservation of the standard BFK09 blindness definition under arbitrary embedding. This is a substantive gap in the current security argument. In the revised manuscript we will add a formal lemma in the security section establishing the required implication: if a local resynthesis satisfies the branch-frame, output-frame, and blinding-behavior conditions, then the joint distribution of all server measurement outcomes on the full pattern remains identical to that of the original BFK09 pattern (hence independent of the client's secret angles). The lemma will be proved by showing that the checks guarantee (i) identical boundary entanglement and (ii) identical local outcome distributions, allowing the original BFK09 blindness argument to carry over unchanged to the composite pattern. We will also update the abstract and main text to reference this lemma explicitly. revision: yes

Circularity Check

0 steps flagged

No circularity; security is explicit compatibility with external BFK09

full rationale

The paper states its security result as a compatibility claim that inherits UBQC blindness from the standard external BFK09 framework without a new trap-soundness theorem or any reduction of the central claim to fitted parameters, self-citations, or definitional loops. The optimization method relies on described post-replacement checks and layer evidence (H-count floor, CNOT-cost floor, etc.) that are presented as independent of the target statistics. No quoted step equates a prediction to its input by construction, and the derivation remains self-contained against the external benchmark of BFK09.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

Abstract-only review; the approach rests on standard UBQC blindness properties and introduces new certification constructs whose independent grounding is not detailed.

axioms (1)

domain assumption BFK09 brickwork patterns and their blindness properties
BPBO claims compatibility with these inherited properties.

invented entities (2)

one-, two-, and three-wire BPBO regions no independent evidence
purpose: Candidate areas for local resynthesis
New detection construct introduced by the paper.
semantic floor and executable witness no independent evidence
purpose: Certification mechanism for each region
New proof/witness objects defined for the optimization.

pith-pipeline@v0.9.1-grok · 5847 in / 1369 out tokens · 38994 ms · 2026-06-30T06:32:51.909457+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

43 extracted references · 27 canonical work pages · 17 internal anchors

[1]

The requirement and the obstruction By the parity-ledger analysis of Sec. V, every phase- gadget realization of CCZ modulo a single-qubit Pauli frame must deposit odd (T-family) phases onall seven parity forms—the deposit syndrome is a representation- independent invariant (Lemma 3, App. A)—and in par- ticular on the threex 0-containing paritiesx 0⊕x1,x 0...
[2]

rotation

How the witness is constructed: two synthesis principles The witness is not a lucky search result; it is produced by a reusable procedure built on two principles. Lemma 1(Frame-chained synthesis).LetT 1, . . . , Tk be per-cell targets withT k · · ·T1 =U. Solve the cells se- quentially againstresidue-adaptedtargets: celljreal- izesP j Gj Tj R† j−1 exactly,...
[3]

Parity-Ledger Necessity For aπ/4-valued diagonal 3-qubit phase function in the CNOT+T/ phase-gadget scope, write the phase over parity forms:φ(x) = π 4 P L cL χL(x) withc L ∈Z 8,L ranging over the seven nonempty subsets of{x 0, x1, x2} andχ L(x) =L i∈L xi. A gadget realization specifies its deposits explicitly, so itcomes witha representationφ= P i ai χLi...
[4]

U∈ R F (n, k) up to the model’s gauge and Pauli-frame dressing

The Supply–Demand Floor (Theorem 1) Proof.LetUadmit ak-cell realization in the classF, i.e. U∈ R F (n, k) up to the model’s gauge and Pauli-frame dressing. Orbit-invariance ofDmakesD(U) well de- fined on the dressed target, and the over-approximation 17 property then placesD(U)∈S(k). By definition of floorD(U),D(U)/∈S(j) for allj <floor D(U). Hence no rea...
[5]

Hence RBFK(1, k) ={h≤2k}for everyk

Wire-Count Instantiations (Corollaries 1, 2) Proof sketch (Corollary 1).Both directions are general ink.Supply(upper bound): one cell’s wire chain isR zHR zHR z—exactly two Hadamards with freeA- phases—sokconcatenated cells realize, by construction, exactly the alternating words with at most 2kHadamards (adjacent phases merge).Demand(achievability): any U...
[6]

Two-Cell Schedule Coverage and Theorem 2 Lemma 4(Coverage).Model a clean two-macro-cell window generously: the two-rung blocks act on their wire pairs byanyelement ofGL(2,F 2)(including SWAP), and odd deposits may be placed on every parity form carried by a wire at a block boundary or inside a block’s two-form span; the net linear action must return to th...
[7]

Verification Protocol of Theorem 3 Proof (verification).The witness is an explicit artifact: three 3×8 angle tables overA(App. B). Verifica- tion separates four layers. First, the floating transfer- matrix contraction on the production geometry equals (Y⊗X⊗Z)·CCZ after global-phase alignment with max- imum elementwise deviation below 10 −15; a brute-force...
[8]

By induc- tion,R j := (U j · · ·U1)(Tj · · ·T1)† =P j Gj: indeed UjRj−1(Tj−1 · · ·T1) =P jGjTj(Tj−1 · · ·T1)

Proof of Lemma 1 (Frame-Chained Synthesis) Proof.DefineR 0 =Iand let celljrealize exactly Uj =P j Gj Tj R† j−1 withP j a Pauli tensor andG j a per-wire Hadamard gauge (G k =I). By induc- tion,R j := (U j · · ·U1)(Tj · · ·T1)† =P j Gj: indeed UjRj−1(Tj−1 · · ·T1) =P jGjTj(Tj−1 · · ·T1). Atj=k, Rk =P k, i.e.U k · · ·U1 =P k (Tk · · ·T1). The residue normal ...
[9]

Proof.In the pattern’s column gauge, columncapplies a diagonal layer (the measurement phases and the rung CZs) followed by a hop Hadamard on every wire

Proof of Theorem 4 (Branch-Frame Closure) The proof rests on four exact single- and two-qubit identities, each verified in isolation: (a)R z(t)X=e it X Rz(−t), (b) CZ (X⊗I) = (X⊗Z) CZ, (c)|− t⟩=|+ t+π⟩, R z(t+π) =R z(t)Z, (d)HX=ZH, HZ=XH. Proof.In the pattern’s column gauge, columncapplies a diagonal layer (the measurement phases and the rung CZs) followe...
[10]

Condition on a public value of δand on the past transcript

Proof of Theorem 5 (Blindness Preservation) Proof.The server-visible protocol view has three compo- nents.Graph: the rewrites introduce no non-standard topology—after materialization the graph is the stan- dard brickwork determined by (n, m′) alone.Angles: per qubit,δ=ϕ ′ +θ+rπwith fresh uniformθon the cyclic groupAand uniformr; thereforeδis uniform and i...
[11]

independent implemen- tation

Proof of Lemma 2 (Round Indistinguishability) Proof.Compare the pre-abort view components across round types at fixed (n, m ′), conditioning on the past transcript.Graph: identical by construction.Received qubits: computation rounds send|+ θ⟩,θuniform (⇒I/2 per qubit); test rounds send dummies|z⟩,zuniform (I/2) or traps|+ θ⟩(I/2); preparations are indepen...
[12]

A. M. Childs, Secure assisted quantum computation, Quantum Information and Computation5, 456 (2005), arXiv:quant-ph/0111046

work page internal anchor Pith review Pith/arXiv arXiv 2005
[13]

Raussendorf and H

R. Raussendorf and H. J. Briegel, A one-way quantum computer, Physical Review Letters86, 5188 (2001)

2001
[14]

Universal blind quantum computation

A. Broadbent, J. Fitzsimons, and E. Kashefi, Univer- sal blind quantum computation, inProc. 50th Annual IEEE Symposium on Foundations of Computer Science 22 (FOCS)(2009) pp. 517–526, arXiv:0807.4154

work page internal anchor Pith review Pith/arXiv arXiv 2009
[15]

J. F. Fitzsimons and E. Kashefi, Unconditionally verifi- able blind quantum computation, Physical Review A96, 012303 (2017), arXiv:1203.5217

work page internal anchor Pith review Pith/arXiv arXiv 2017
[16]

Leichtle, L

D. Leichtle, L. Music, E. Kashefi, and H. Ollivier, Verifying BQP computations on noisy devices with minimal overhead, PRX Quantum2, 040302 (2021), arXiv:2109.04042

work page arXiv 2021
[17]

Drmota, D

P. Drmota, D. P. Nadlinger, D. Main, B. C. Nichol, E. M. Ainley, D. Leichtle, A. Mantri, E. Kashefi, R. Srinivas, G. Araneda, C. J. Ballance, and D. M. Lucas, Verifiable blind quantum computing with trapped ions and single photons, Physical Review Letters132, 150604 (2024), arXiv:2305.02936

work page arXiv 2024
[18]

Polacchi, D

B. Polacchi, D. Leichtle, G. Carvacho, G. Milani, N. Spagnolo, M. Kaplan, E. Kashefi, and F. Sciarrino, Experimental verifiable multiclient blind quantum com- puting on a Qline architecture, Physical Review Letters 134, 200603 (2025)

2025
[19]

The Measurement Calculus

V. Danos, E. Kashefi, and P. Panangaden, The mea- surement calculus, Journal of the ACM54, 8 (2007), arXiv:0704.1263

work page internal anchor Pith review Pith/arXiv arXiv 2007
[20]

Simmons, Relating measurement patterns to circuits via Pauli flow (2021), arXiv:2109.05654 [quant-ph]

W. Simmons, Relating measurement patterns to circuits via Pauli flow (2021), arXiv:2109.05654 [quant-ph]

work page arXiv 2021
[21]

McElvanney and M

T. McElvanney and M. Backens, Complete flow- preserving rewrite rules for MBQC patterns with Pauli measurements (2022), arXiv:2205.02009 [quant-ph]

work page arXiv 2022
[22]

Sunami and M

S. Sunami and M. Fukushima, Graphix: optimizing and simulating measurement-based quantum computation on local-Clifford decorated graph (2022), arXiv:2212.11975

work page arXiv 2022
[23]

Duncan, A

R. Duncan, A. Kissinger, S. Perdrix, and J. van de We- tering, Graph-theoretic simplification of quantum cir- cuits with the ZX-calculus, Quantum4, 279 (2020), arXiv:1902.03178

work page arXiv 2020
[24]

M. Amy, D. Maslov, and M. Mosca, Polynomial-time T- depth optimization of Clifford+T circuits via matroid partitioning, IEEE Transactions on Computer-Aided De- sign of Integrated Circuits and Systems33, 1476 (2014), arXiv:1303.2042

work page internal anchor Pith review Pith/arXiv arXiv 2014
[25]

DeCross, E

M. DeCross, E. Chertkov, M. Kohagen, and M. Foss- Feig, Qubit-reuse compilation with mid-circuit measure- ment and reset, Physical Review X13, 041057 (2023), arXiv:2210.08039

work page arXiv 2023
[26]

Simulation of Two-Qubit Grover Algorithm in MBQC with Universal Blind Quantum Computation

Y. Lee and D. Chung, Simulation of two-qubit Grover algorithm in MBQC with universal blind quantum com- putation (2025), arXiv:2503.09099 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2025
[27]

D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, Generalized flow and determinism in measurement-based quantum computation, New Journal of Physics9, 250 (2007), arXiv:quant-ph/0702212

work page internal anchor Pith review Pith/arXiv arXiv 2007
[28]

Improved Simulation of Stabilizer Circuits

S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A70, 052328 (2004), arXiv:quant-ph/0406196

work page internal anchor Pith review Pith/arXiv arXiv 2004
[29]

The Heisenberg Representation of Quantum Computers

D. Gottesman, The Heisenberg representation of quan- tum computers (1998), arXiv:quant-ph/9807006

work page internal anchor Pith review Pith/arXiv arXiv 1998
[30]

Cowtan, S

A. Cowtan, S. Dilkes, R. Duncan, W. Simmons, and S. Sivarajah, Phase gadget synthesis for shallow circuits, Electronic Proceedings in Theoretical Computer Science 318, 213 (2020), arXiv:1906.01734

work page arXiv 2020
[31]

Nonlocal properties of two-qubit gates and mixed states and optimization of quantum computations

Y. Makhlin, Nonlocal properties of two-qubit gates and mixed states and optimization of quantum computa- tions, Quantum Information Processing1, 243 (2002), arXiv:quant-ph/0002045

work page internal anchor Pith review Pith/arXiv arXiv 2002
[32]

V. V. Shende, S. S. Bullock, and I. L. Markov, Syn- thesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Sys- tems25, 1000 (2006), arXiv:quant-ph/0406176

work page internal anchor Pith review Pith/arXiv arXiv 2006
[33]

L. K. Grover, A fast quantum mechanical algorithm for database search, inProc. 28th Annual ACM Symposium on Theory of Computing (STOC)(1996) pp. 212–219, arXiv:quant-ph/9605043

work page internal anchor Pith review Pith/arXiv arXiv 1996
[34]

Gheorghiu, T

A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verifi- cation of quantum computation: An overview of exist- ing approaches, Theory of Computing Systems63, 715 (2019)

2019
[35]

S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsi- mons, A. Zeilinger, and P. Walther, Demonstration of blind quantum computing, Science335, 303 (2012), arXiv:1110.1381

work page internal anchor Pith review Pith/arXiv arXiv 2012
[36]

Optimal Blind Quantum Computation

A. Mantri, C. A. P´ erez-Delgado, and J. F. Fitzsimons, Optimal blind quantum computation, Physical Review Letters111, 230502 (2013), arXiv:1306.3677

work page internal anchor Pith review Pith/arXiv arXiv 2013
[37]

Mahadev, Classical verification of quantum computa- tions, inProc

U. Mahadev, Classical verification of quantum computa- tions, inProc. 59th Annual IEEE Symposium on Founda- tions of Computer Science (FOCS)(2018) pp. 259–267, arXiv:1804.01082

work page arXiv 2018
[38]

Chien, R

C.-H. Chien, R. Van Meter, and S.-Y. Kuo, Fault-tolerant operations for universal blind quantum computation, ACM Journal on Emerging Technologies in Computing Systems12, 9 (2015), arXiv:1306.3664

work page arXiv 2015
[39]

Yang, M.-Q

Z. Yang, M.-Q. Bai, and Z. Mo, The brickwork state with fewer qubits in blind quantum computation, Quantum Information Processing21, 125 (2022)

2022
[40]

S. Ma, C. Zhu, X. Liu, H. Li, and S. Li, Universal blind quantum computation with improved brickwork states, Physical Review A109, 012606 (2024)

2024
[41]

Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

V. Kliuchnikov, D. Maslov, and M. Mosca, Fast and ef- ficient exact synthesis of single qubit unitaries generated by Clifford and T gates, Quantum Information and Com- putation13, 607 (2013), arXiv:1206.5236

work page internal anchor Pith review Pith/arXiv arXiv 2013
[42]

N. J. Ross and P. Selinger, Optimal ancilla-free Clif- ford+T approximation ofz-rotations, Quantum Informa- tion and Computation16, 901 (2016), arXiv:1403.2975

work page internal anchor Pith review Pith/arXiv arXiv 2016
[43]

Quantum computing with Qiskit

A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum computing with Qiskit (2024), arXiv:2405.08810 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2024

[1] [1]

The requirement and the obstruction By the parity-ledger analysis of Sec. V, every phase- gadget realization of CCZ modulo a single-qubit Pauli frame must deposit odd (T-family) phases onall seven parity forms—the deposit syndrome is a representation- independent invariant (Lemma 3, App. A)—and in par- ticular on the threex 0-containing paritiesx 0⊕x1,x 0...

[2] [2]

rotation

How the witness is constructed: two synthesis principles The witness is not a lucky search result; it is produced by a reusable procedure built on two principles. Lemma 1(Frame-chained synthesis).LetT 1, . . . , Tk be per-cell targets withT k · · ·T1 =U. Solve the cells se- quentially againstresidue-adaptedtargets: celljreal- izesP j Gj Tj R† j−1 exactly,...

[3] [3]

Parity-Ledger Necessity For aπ/4-valued diagonal 3-qubit phase function in the CNOT+T/ phase-gadget scope, write the phase over parity forms:φ(x) = π 4 P L cL χL(x) withc L ∈Z 8,L ranging over the seven nonempty subsets of{x 0, x1, x2} andχ L(x) =L i∈L xi. A gadget realization specifies its deposits explicitly, so itcomes witha representationφ= P i ai χLi...

[4] [4]

U∈ R F (n, k) up to the model’s gauge and Pauli-frame dressing

The Supply–Demand Floor (Theorem 1) Proof.LetUadmit ak-cell realization in the classF, i.e. U∈ R F (n, k) up to the model’s gauge and Pauli-frame dressing. Orbit-invariance ofDmakesD(U) well de- fined on the dressed target, and the over-approximation 17 property then placesD(U)∈S(k). By definition of floorD(U),D(U)/∈S(j) for allj <floor D(U). Hence no rea...

[5] [5]

Hence RBFK(1, k) ={h≤2k}for everyk

Wire-Count Instantiations (Corollaries 1, 2) Proof sketch (Corollary 1).Both directions are general ink.Supply(upper bound): one cell’s wire chain isR zHR zHR z—exactly two Hadamards with freeA- phases—sokconcatenated cells realize, by construction, exactly the alternating words with at most 2kHadamards (adjacent phases merge).Demand(achievability): any U...

[6] [6]

Two-Cell Schedule Coverage and Theorem 2 Lemma 4(Coverage).Model a clean two-macro-cell window generously: the two-rung blocks act on their wire pairs byanyelement ofGL(2,F 2)(including SWAP), and odd deposits may be placed on every parity form carried by a wire at a block boundary or inside a block’s two-form span; the net linear action must return to th...

[7] [7]

Verification Protocol of Theorem 3 Proof (verification).The witness is an explicit artifact: three 3×8 angle tables overA(App. B). Verifica- tion separates four layers. First, the floating transfer- matrix contraction on the production geometry equals (Y⊗X⊗Z)·CCZ after global-phase alignment with max- imum elementwise deviation below 10 −15; a brute-force...

[8] [8]

By induc- tion,R j := (U j · · ·U1)(Tj · · ·T1)† =P j Gj: indeed UjRj−1(Tj−1 · · ·T1) =P jGjTj(Tj−1 · · ·T1)

Proof of Lemma 1 (Frame-Chained Synthesis) Proof.DefineR 0 =Iand let celljrealize exactly Uj =P j Gj Tj R† j−1 withP j a Pauli tensor andG j a per-wire Hadamard gauge (G k =I). By induc- tion,R j := (U j · · ·U1)(Tj · · ·T1)† =P j Gj: indeed UjRj−1(Tj−1 · · ·T1) =P jGjTj(Tj−1 · · ·T1). Atj=k, Rk =P k, i.e.U k · · ·U1 =P k (Tk · · ·T1). The residue normal ...

[9] [9]

Proof.In the pattern’s column gauge, columncapplies a diagonal layer (the measurement phases and the rung CZs) followed by a hop Hadamard on every wire

Proof of Theorem 4 (Branch-Frame Closure) The proof rests on four exact single- and two-qubit identities, each verified in isolation: (a)R z(t)X=e it X Rz(−t), (b) CZ (X⊗I) = (X⊗Z) CZ, (c)|− t⟩=|+ t+π⟩, R z(t+π) =R z(t)Z, (d)HX=ZH, HZ=XH. Proof.In the pattern’s column gauge, columncapplies a diagonal layer (the measurement phases and the rung CZs) followe...

[10] [10]

Condition on a public value of δand on the past transcript

Proof of Theorem 5 (Blindness Preservation) Proof.The server-visible protocol view has three compo- nents.Graph: the rewrites introduce no non-standard topology—after materialization the graph is the stan- dard brickwork determined by (n, m′) alone.Angles: per qubit,δ=ϕ ′ +θ+rπwith fresh uniformθon the cyclic groupAand uniformr; thereforeδis uniform and i...

[11] [11]

independent implemen- tation

Proof of Lemma 2 (Round Indistinguishability) Proof.Compare the pre-abort view components across round types at fixed (n, m ′), conditioning on the past transcript.Graph: identical by construction.Received qubits: computation rounds send|+ θ⟩,θuniform (⇒I/2 per qubit); test rounds send dummies|z⟩,zuniform (I/2) or traps|+ θ⟩(I/2); preparations are indepen...

[12] [12]

A. M. Childs, Secure assisted quantum computation, Quantum Information and Computation5, 456 (2005), arXiv:quant-ph/0111046

work page internal anchor Pith review Pith/arXiv arXiv 2005

[13] [13]

Raussendorf and H

R. Raussendorf and H. J. Briegel, A one-way quantum computer, Physical Review Letters86, 5188 (2001)

2001

[14] [14]

Universal blind quantum computation

A. Broadbent, J. Fitzsimons, and E. Kashefi, Univer- sal blind quantum computation, inProc. 50th Annual IEEE Symposium on Foundations of Computer Science 22 (FOCS)(2009) pp. 517–526, arXiv:0807.4154

work page internal anchor Pith review Pith/arXiv arXiv 2009

[15] [15]

J. F. Fitzsimons and E. Kashefi, Unconditionally verifi- able blind quantum computation, Physical Review A96, 012303 (2017), arXiv:1203.5217

work page internal anchor Pith review Pith/arXiv arXiv 2017

[16] [16]

Leichtle, L

D. Leichtle, L. Music, E. Kashefi, and H. Ollivier, Verifying BQP computations on noisy devices with minimal overhead, PRX Quantum2, 040302 (2021), arXiv:2109.04042

work page arXiv 2021

[17] [17]

Drmota, D

P. Drmota, D. P. Nadlinger, D. Main, B. C. Nichol, E. M. Ainley, D. Leichtle, A. Mantri, E. Kashefi, R. Srinivas, G. Araneda, C. J. Ballance, and D. M. Lucas, Verifiable blind quantum computing with trapped ions and single photons, Physical Review Letters132, 150604 (2024), arXiv:2305.02936

work page arXiv 2024

[18] [18]

Polacchi, D

B. Polacchi, D. Leichtle, G. Carvacho, G. Milani, N. Spagnolo, M. Kaplan, E. Kashefi, and F. Sciarrino, Experimental verifiable multiclient blind quantum com- puting on a Qline architecture, Physical Review Letters 134, 200603 (2025)

2025

[19] [19]

The Measurement Calculus

V. Danos, E. Kashefi, and P. Panangaden, The mea- surement calculus, Journal of the ACM54, 8 (2007), arXiv:0704.1263

work page internal anchor Pith review Pith/arXiv arXiv 2007

[20] [20]

Simmons, Relating measurement patterns to circuits via Pauli flow (2021), arXiv:2109.05654 [quant-ph]

W. Simmons, Relating measurement patterns to circuits via Pauli flow (2021), arXiv:2109.05654 [quant-ph]

work page arXiv 2021

[21] [21]

McElvanney and M

T. McElvanney and M. Backens, Complete flow- preserving rewrite rules for MBQC patterns with Pauli measurements (2022), arXiv:2205.02009 [quant-ph]

work page arXiv 2022

[22] [22]

Sunami and M

S. Sunami and M. Fukushima, Graphix: optimizing and simulating measurement-based quantum computation on local-Clifford decorated graph (2022), arXiv:2212.11975

work page arXiv 2022

[23] [23]

Duncan, A

R. Duncan, A. Kissinger, S. Perdrix, and J. van de We- tering, Graph-theoretic simplification of quantum cir- cuits with the ZX-calculus, Quantum4, 279 (2020), arXiv:1902.03178

work page arXiv 2020

[24] [24]

M. Amy, D. Maslov, and M. Mosca, Polynomial-time T- depth optimization of Clifford+T circuits via matroid partitioning, IEEE Transactions on Computer-Aided De- sign of Integrated Circuits and Systems33, 1476 (2014), arXiv:1303.2042

work page internal anchor Pith review Pith/arXiv arXiv 2014

[25] [25]

DeCross, E

M. DeCross, E. Chertkov, M. Kohagen, and M. Foss- Feig, Qubit-reuse compilation with mid-circuit measure- ment and reset, Physical Review X13, 041057 (2023), arXiv:2210.08039

work page arXiv 2023

[26] [26]

Simulation of Two-Qubit Grover Algorithm in MBQC with Universal Blind Quantum Computation

Y. Lee and D. Chung, Simulation of two-qubit Grover algorithm in MBQC with universal blind quantum com- putation (2025), arXiv:2503.09099 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2025

[27] [27]

D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, Generalized flow and determinism in measurement-based quantum computation, New Journal of Physics9, 250 (2007), arXiv:quant-ph/0702212

work page internal anchor Pith review Pith/arXiv arXiv 2007

[28] [28]

Improved Simulation of Stabilizer Circuits

S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A70, 052328 (2004), arXiv:quant-ph/0406196

work page internal anchor Pith review Pith/arXiv arXiv 2004

[29] [29]

The Heisenberg Representation of Quantum Computers

D. Gottesman, The Heisenberg representation of quan- tum computers (1998), arXiv:quant-ph/9807006

work page internal anchor Pith review Pith/arXiv arXiv 1998

[30] [30]

Cowtan, S

A. Cowtan, S. Dilkes, R. Duncan, W. Simmons, and S. Sivarajah, Phase gadget synthesis for shallow circuits, Electronic Proceedings in Theoretical Computer Science 318, 213 (2020), arXiv:1906.01734

work page arXiv 2020

[31] [31]

Nonlocal properties of two-qubit gates and mixed states and optimization of quantum computations

Y. Makhlin, Nonlocal properties of two-qubit gates and mixed states and optimization of quantum computa- tions, Quantum Information Processing1, 243 (2002), arXiv:quant-ph/0002045

work page internal anchor Pith review Pith/arXiv arXiv 2002

[32] [32]

V. V. Shende, S. S. Bullock, and I. L. Markov, Syn- thesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Sys- tems25, 1000 (2006), arXiv:quant-ph/0406176

work page internal anchor Pith review Pith/arXiv arXiv 2006

[33] [33]

L. K. Grover, A fast quantum mechanical algorithm for database search, inProc. 28th Annual ACM Symposium on Theory of Computing (STOC)(1996) pp. 212–219, arXiv:quant-ph/9605043

work page internal anchor Pith review Pith/arXiv arXiv 1996

[34] [34]

Gheorghiu, T

A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verifi- cation of quantum computation: An overview of exist- ing approaches, Theory of Computing Systems63, 715 (2019)

2019

[35] [35]

S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsi- mons, A. Zeilinger, and P. Walther, Demonstration of blind quantum computing, Science335, 303 (2012), arXiv:1110.1381

work page internal anchor Pith review Pith/arXiv arXiv 2012

[36] [36]

Optimal Blind Quantum Computation

A. Mantri, C. A. P´ erez-Delgado, and J. F. Fitzsimons, Optimal blind quantum computation, Physical Review Letters111, 230502 (2013), arXiv:1306.3677

work page internal anchor Pith review Pith/arXiv arXiv 2013

[37] [37]

Mahadev, Classical verification of quantum computa- tions, inProc

U. Mahadev, Classical verification of quantum computa- tions, inProc. 59th Annual IEEE Symposium on Founda- tions of Computer Science (FOCS)(2018) pp. 259–267, arXiv:1804.01082

work page arXiv 2018

[38] [38]

Chien, R

C.-H. Chien, R. Van Meter, and S.-Y. Kuo, Fault-tolerant operations for universal blind quantum computation, ACM Journal on Emerging Technologies in Computing Systems12, 9 (2015), arXiv:1306.3664

work page arXiv 2015

[39] [39]

Yang, M.-Q

Z. Yang, M.-Q. Bai, and Z. Mo, The brickwork state with fewer qubits in blind quantum computation, Quantum Information Processing21, 125 (2022)

2022

[40] [40]

S. Ma, C. Zhu, X. Liu, H. Li, and S. Li, Universal blind quantum computation with improved brickwork states, Physical Review A109, 012606 (2024)

2024

[41] [41]

Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

V. Kliuchnikov, D. Maslov, and M. Mosca, Fast and ef- ficient exact synthesis of single qubit unitaries generated by Clifford and T gates, Quantum Information and Com- putation13, 607 (2013), arXiv:1206.5236

work page internal anchor Pith review Pith/arXiv arXiv 2013

[42] [42]

N. J. Ross and P. Selinger, Optimal ancilla-free Clif- ford+T approximation ofz-rotations, Quantum Informa- tion and Computation16, 901 (2016), arXiv:1403.2975

work page internal anchor Pith review Pith/arXiv arXiv 2016

[43] [43]

Quantum computing with Qiskit

A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum computing with Qiskit (2024), arXiv:2405.08810 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2024