Pith. sign in

REVIEW 1 major objections 4 minor 60 references

Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a teleportation-based quantum homomorphic encryption scheme can be rewritten as a classical-quantum circuit whose encryption key is updated at run time, making the number of classically controlled S gates linear in…

desk verdict The simulation machinery is a real step forward for QHE testing, but the X-only QOTP security claim in Sec. III.C is wrong for the pure-state encodings used in the semiclassical walk. read the letter →

arxiv 2412.01966 v2 pith:DHZTJHCM submitted 2024-12-02 quant-ph

Sergio A. Ortega , Pablo Fernández , Miguel A. Martin-Delgado This is my paper · ORCID
classification quant-ph MSC 81P68 PACS 03.67.Lx
keywords quantumhomomorphicencryptionclassical-quantumcircuitsSzegedywalksemiclassicalClifford+Tgatecomplexityruntimekeyupdatingmeasurementandresetcircuitsimulation
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

Quantum homomorphic encryption lets an untrusted server run a circuit on encrypted qubits, but in the leading teleportation-based schemes the client's decryption key for each T gate depends on a measurement outcome, and earlier simulations handled this by precomputing an exponential number of key mappings. This paper claims that the whole scheme can be rewritten as a classical-quantum circuit in which the key is updated at run time, gate by gate, so the number of classically controlled S gates grows linearly with the number of $T/T^\dagger$ gates. The same circuit treatment is extended to intermediate measurements and resets, which are exactly the operations a semiclassical quantum walk needs. If the claim is correct, homomorphic evaluation of Szegedy quantum and semiclassical walks becomes practical to simulate, and the construction gives a reusable recipe for other low-T-gate algorithms.

What carries the argument

The load-bearing object is the table of key-updating functions and their classical-quantum circuit implementation. For each Clifford gate the update is a classical operation over the XOR-encoded key bits; for each $T/T^\dagger$ gate the update is a classical-quantum procedure in which the client measures a Bell register in an $S^a$-rotated basis and feeds the outcome bits back into the key. The paper's second mechanism is the simplified simulation: by invoking the principle of deferred measurements, the Bell registers can be measured and reset immediately after each $T$ gate, so two ancilla qubits serve all $T$ gates and the memory cost no longer grows with the circuit's $T$-gate count. These rules together make the encryption key an explicitly dynamical quantity of the circuit rather than a precomputed object.

What would settle it

Run any Clifford+T circuit through both the full scheme, with one Bell register per $T/T^\dagger$ gate measured after the main circuit, and the simplified scheme, with two Bell ancillas measured and reset after each $T/T^\dagger$ gate, forcing identical initial keys and identical Bell-outcome bits in both runs, then compare the decrypted output distributions; any difference beyond sampling noise would show that the interleaved measurement and reset altered the main-qubit evolution.

Watch

Extended reading notes

Core claim

The central claim is that the decryption phase of the teleportation-based QHE scheme can be built as a classical-quantum circuit instead of an exponential table lookup. Each Clifford gate contributes a deterministic update on the classical key bits $x$ and $z$; each $T$ gate contributes a teleported $S^a$ correction whose control bit $a$ is the current key bit, plus two fresh randomness bits from an $S^a$-rotated Bell measurement; each $T^\dagger$ gate contributes the analogous update. Because these updates are executed in order during simulation, the final key is obtained when the circuit is run, not before it, and the number of classically controlled S gates is one per $T/T^\dagger$ gate. The paper also provides key-updating rules for measurement and reset, and shows that the $T/T^\dagger$-gate counts for Szegedy walk circuits on cycle, complete, and complete bipartite graphs grow polylogarithmically or logarithmically in the number of nodes, so the schemes are efficient for those walks. Simulations on small instances reproduce the deterministic walk probabilities after decryption.

Load-bearing premise

The simplified simulation assumes that measuring and resetting the Bell ancilla qubits immediately after each T gate, instead of storing every Bell register until the end, leaves the main qubits' evolution exactly unchanged; if the early measurement disturbs the state or produces ordering effects, the semiclassical-walk simulation would not faithfully represent the QHE protocol.

Editorial extensions

If this is right

  • Circuits with polynomially many $T/T^\dagger$ gates can be evaluated homomorphically without exponential key precomputation; the client's work scales with the circuit size.
  • Homomorphic evaluation extends to circuits containing intermediate measurements and resets, so semiclassical walks and other algorithms with mid-circuit measurements become valid QHE workloads.
  • The Szegedy walk circuits considered here have polylogarithmic or logarithmic $T/T^\dagger$ counts in the number of graph nodes, so homomorphic evaluation of these walks is efficient rather than asymptotically prohibitive.
  • The simplified two-ancilla simulation makes the memory footprint of a classical QHE simulation independent of the number of $T/T^\dagger$ gates, enabling larger test circuits in classical simulators.
  • The reusable circuit blocks form a library for building and testing QHE implementations of other Clifford+T algorithms.

Reading between the lines

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

  • Beyond the paper, the same gate-by-gate key update should generalize to any gate-teleportation QHE scheme whose corrections are Clifford operations conditioned on measurement bits; the scheme's practical limit is the client's classical processing speed, not the quantum resource count.
  • Because the semiclassical walk is adaptive, with each step's initial state depending on the previous measurement, the reset and measurement rules imply that limited classes of adaptive quantum circuits can be run homomorphically, not only fixed-depth ones; this is directly testable on repeated-measurement algorithms.
  • The $T$-count analysis points to the update operator $V$ as the real cost driver: graphs with structured transition matrices admitting efficient $V$ circuits will be the natural targets for QHE, while irregular Markov chains should be expected to break the polylogarithmic scaling.
  • The two-ancilla simplification, if it holds exactly, also suggests a hardware-level resource trade: mid-circuit measurement and qubit reuse could let QHE run on small devices with fixed qubit counts, at the price of deeper circuits and measurement errors.
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

1 major / 4 minor

Summary. The paper reformulates Liang's quasi-compact quantum homomorphic encryption scheme as a classical-quantum circuit in which the encryption key is updated at running time, avoiding the exponential precomputation of key-updating functions used in earlier Qiskit implementations. It derives key-updating functions for Clifford gates, T/T† gates, measurement, and reset; analyzes T/T† counts for Szegedy quantum walks on cycle, complete, and bipartite graphs; and reports Qiskit simulations of a quantum walk on a bipartite graph and a semiclassical walk on a cycle, benchmarked against the SQUWALS simulator. The paper also introduces the CQC-QHE library for constructing and simulating such circuits.

Significance. If the security and correctness claims hold, the paper is a useful contribution to the practical simulation of QHE schemes. The key-updating derivations are self-contained and correct, the T-count formulas check out, and the simulations are cross-checked against an independent deterministic simulator (SQUWALS) and an unencrypted circuit. The reformulation with a linear number of classically controlled S gates is a genuine improvement over previous exponential precomputation approaches. However, one load-bearing security claim is flawed for the pure-state initializations actually used in the semiclassical simulations, and this needs to be addressed before the results can be accepted as stated.

major comments (1)
  1. [III.C (Eq. 38)] The perfect-security argument for X-only QOTP is valid only for states that are diagonal in the computational basis, but the text explicitly claims that the argument covers quantum superpositions. For the pure state |ψ⟩ = √p|0⟩ + √(1−p)|1⟩ used in the semiclassical simulation (Section V, cycle graph, initial vector (0.75, 0.25, 0, ...), created by an RY gate), the X-averaged ciphertext is ρ = (1/2)∑_a X^a|ψ⟩⟨ψ|X^a = (1/2)I + √(p(1−p))(|0⟩⟨1| + |1⟩⟨0|), whose trace distance from the maximally mixed state is √(p(1−p)) ≠ 0. A server can measure in the {|+⟩,|−⟩} basis and estimate p, so the protocol is not perfectly secure for such inputs. The final equality in Eq. (38) uses ρ_c = Z_iρ_cZ_i†, which is false for a coherent superposition; it holds only for the diagonal mixed state of Eq. (37). This is load-bearing because the abstract and Section VI claim perfect security for the semiclassical walk implementation, and the simulations initialize the walker in a pure superposition. The fix is to encrypt pure initial states with the full X+Z QOTP of Eq. (21), or to restrict the security claim and the simulations to diagonal mixed-state inputs; the former is preferable and is compatible with the rest of the scheme.
minor comments (4)
  1. [IV.B (Eq. 52)] The identity H = A X A† with A = SHT H S†H is stated without proof; the identity is correct, but a short derivation or an explicit reference would make the +2 T/T† cost in Eq. (52) easier to verify.
  2. [SM SII] The equivalence between the full L-ancilla simulation and the simplified two-ancilla simulation is demonstrated only empirically in SM Figure S8; a short formal argument invoking the deferred-measurement principle would strengthen Section V, since the semiclassical walk results use the simplified simulation.
  3. [II.D (Eq. 22)] The complexity expression in Eq. (22) refers to the composed Clifford key-updating functions, while the Qiskit implementation uses one key-updating function per gate; this distinction is acknowledged in Section VI but should be stated at the point of Eq. (22) to avoid confusion.
  4. [General] There are typographical issues such as 'SQUW ALS' for SQUWALS and inconsistent spacing in 'T /T†'; also, the notation log2(N) is used for log_2(N) and should be made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: key-updating rules and T-gate counts are derived from gate commutation and circuit decompositions, and the QHE simulations are validated against an independent Szegedy-walk simulator rather than fitted.

full rationale

The paper's central derivation is self-contained and does not reduce to its inputs. The key-updating functions (Eqs. 9, 11, 14, 16, 18, 20) are obtained by direct gate-commutation identities, e.g. Eq. (17) T X^a Z^b = (S^dagger)^a X^a Z^{a xor b} T, so the classical keys are computed from the circuit, not fitted from the outputs. The claimed linear-in-L number of classically controlled S gates follows from associating one S^a measurement correction per T/T^dagger gate and from composing Clifford updates (Eq. 22); it does not depend on the final encrypted results. The T/T^dagger counts for the walks are derived from standard multi-controlled-gate decompositions and from the update-operator circuits (Eqs. 45-47, 57-58, 64-66); these are circuit identities, not fits. The simulation validation compares decrypted Qiskit samples with SQUWALS [43] deterministic walk distributions; SQUWALS computes the walk from the transition matrix and unitary evolution, so no parameter inside the QHE circuit is fitted and then renamed as a prediction. The self-citations (SQUWALS, semiclassical-walk equivalence, prior walk circuits) are used as benchmarks or background, not as the justification of the QHE key-update mechanism. The X-only QOTP security argument in Sec. III.C is questionable for the pure positive-superposition initializations used in the simulations, because off-diagonal coherences survive X-only averaging; however, this is a soundness gap rather than circularity, since Eq. (38) is a direct identity for diagonal rho_c and is not derived from the walk results. No load-bearing step in the derivation chain is equivalent to its own input.

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

The paper contributes no fitted parameters and no invented entities. It relies on standard results in quantum information: QOTP security, gate teleportation, known decompositions of multi-controlled gates, Solovay-Kitaev approximation, and the circuit constructions from Loke and Wang. The main load-bearing external input is the correctness of the update operator circuits and the decompositions used in the T-count.

assumptions (6)
  • standard math Quantum one-time pad with random keys yields a perfectly secure encryption, giving the totally mixed state (Eq. 21).
    Invoked in Section II.D to establish perfect security of the QHE scheme and in Section III.C for the X-only encryption of classical distributions.
  • standard math Gate teleportation with a U-rotated Bell basis teleports X^a Z^b U |psi> to the receiver (Eq. B3).
    Used in Section II.B for the homomorphic T-gate evaluation.
  • domain assumption Multi-controlled X gates with n_c controls decompose into 2 n_c - 3 Toffoli gates, each costing 7 T/T† gates; multi-controlled U gates decompose as in Figure 7(b).
    Used throughout Section IV for the T-count analysis; relies on standard circuit decompositions from the literature.
  • standard math Any single-qubit rotation RZ (and hence RY) can be approximated in Clifford+T with O(log(1/epsilon)) T gates (Solovay-Kitaev and Ross-Selinger).
    Used in Section IV.B to bound L_R and support the claim that the complete graph walk is efficiently implementable.
  • domain assumption The principle of deferred measurements allows the Sa-rotated Bell measurements to be postponed until the end of the circuit, or performed early in the simplified simulation without changing the final state.
    Used in Section II.B and SM Section SII to justify reusing Bell qubits in the simulation.
  • domain assumption The update operator V circuits for cycle, complete, and bipartite graphs (Figures 10, 12, 15) correctly implement the Szegedy walk operator; a correctness proof is given for the bipartite circuit in SM Section SIII.
    Used in Section IV to derive T-count formulas; cycle and complete graph circuits are taken from the literature [49].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption." pith.science (2026). https://pith.science/paper/DHZTJHCM

@misc{pith2026241201966,
  author       = {Pith},
  title        = {Pith review of: Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DHZTJHCM}},
  note         = {Machine review of arXiv:2412.01966}
}
abstract

As cloud services continue to expand, the security of private data stored and processed in these environments has become paramount. This work delves into quantum homomorphic encryption (QHE), an emerging technology that facilitates secure computation on encrypted quantum data without revealing the underlying information. We reinterpret QHE schemes through classical-quantum circuits, enhancing efficiency and addressing previous limitations related to key computations. Our approach eliminates the need for exponential key preparation by calculating keys in real-time during simulation, leading to a linear complexity in classically controlled gates. We also investigate the $T/T^{\dagger}$-gate complexity associated with various quantum walks, particularly Szegedy quantum and semiclassical algorithms, demonstrating efficient homomorphic implementations across different graph structures. Our simulations, conducted in Qiskit, validate the effectiveness of QHE for both standard and semiclassical walks. The rules for the homomorphic evaluation of the reset and intermediate measurement operations have also been included to perform the QHE of semiclassical walks. Additionally, we introduce the CQC-QHE library, a comprehensive tool that simplifies the construction and simulation of classical-quantum circuits tailored for quantum homomorphic encryption. Future work will focus on optimizing classical functions within this framework and exploring broader graph types to enhance QHE applications in practical scenarios.

Figures

Figures reproduced from arXiv: 2412.01966 by the authors.

Figure 1
Figure 1. Homomorphic evaluation scheme for a T gate using gate teleportation. Besides the T gate, a swap gate, Clifford gates and measurements are performed. The part on the left of the red line is performed by Server, and the part on the right by Client once Server has finished running the quantum algorithm. There are two differences with the actual gate teleportation protocol. In gate teleportation Server would have to app… view at source ↗
Figure 2
Figure 2. Example of a quantum algorithm with 2 T /T† gates and Clifford gates applied to two qubits. The block denoted by “Init” is an algorithm used by Client to create the initial state sent to Server. Its homomorphic implementation is not relevant since it is not performed by Server. The remaining Clifford+T gates constitute Server’s algorithm. The last step is measuring each qubit. From this elementary but representative… view at source ↗
Figure 3
Figure 3. Circuits for the three steps of the quantum homomorphic encryption scheme applied to the example in Figure [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Quantum circuit for the semiclassical Szegedy walk. The walk is performed [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: General quantum circuit for the unitary evolution operator [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Quantum circuit for the diagonal operator [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: a) Decomposition of a multi-controlled-X operation that contains nc = 5 control qubits into 2nc −3 = 7 Toffoli gates using nc − 2 = 3 ancilla qubits. b) Decomposition of a multi-controlled-U operation that contains nc = 5 control qubits into 2nc − 2 = 8 Toffoli gates a…
Figure 8
Figure 8. Figure 8: Decomposition of a Toffoli gate into Clifford+ [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Representation of different types of graphs with symmetry. a) Cycle graph with [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: Quantum circuit for the update operator V for Szegedy quantum walk over a cycle graph. . . . m P + = . . . · · · . . . m [PITH_FULL_IMAGE:figures/full_fig_p017_10.png]
Figure 11
Figure 11. Figure 11: Quantum circuit for a controlled-P + operator acting over m qubits. of the cycle graph: LU = 14 3 n 3 − 7n 2 + 49 3 n − 35. (46) Finally, we use that n = log2 (N) to express LU in terms of the number of nodes: LU = 14 3 log3 2 (N) − 7 log2 2 (N) + 49 3 log2 (N) − 35. …
Figure 12
Figure 12. Figure 12: Quantum circuit for the update operator V for Szegedy quantum walk over a complete graph. The quantum circuit for the update operator V [49] is shown in [PITH_FULL_IMAGE:figures/full_fig_p018_12.png]
Figure 13
Figure 13. Figure 13: Quantum circuit for the operator Ve in [PITH_FULL_IMAGE:figures/full_fig_p019_13.png]
Figure 14
Figure 14. Figure 14: Decomposition of a single-controlled-RY gate into two CNOT gates and two RY gates. Adding all the contributions in (50) we obtain the number of T /T† gates for the operator Ve: LVe = 15n 2 − 43n + 14 + (2n − 3)LR. (56) Substituting in (49) we obtain the number of T /T…
Figure 15
Figure 15. Figure 15: Quantum circuit for the update operator V for Szegedy quantum walk over a complete bipartite graph. We have slightly modified the circuit found in the literature [49] in the case of the bipartite graph in order to obtain a single update operator V as per [PITH_FULL_I…
Figure 16
Figure 16. Figure 16: Quantum circuit for Szegedy quantum walk over a bipartite graph with [PITH_FULL_IMAGE:figures/full_fig_p023_16.png]
Figure 17
Figure 17. Figure 17: Probability distributions of the walker for the quantum walk over the bipartite graph using the QHE scheme and [PITH_FULL_IMAGE:figures/full_fig_p024_17.png]
Figure 18
Figure 18. Figure 18: Semiclassical graph for the semiclassical walk over the cycle with [PITH_FULL_IMAGE:figures/full_fig_p025_18.png]
Figure 19
Figure 19. Figure 19: Quantum circuit for gate teleportation. The box represents the quantum measurement Alice performs on the qubit [PITH_FULL_IMAGE:figures/full_fig_p030_19.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 57 canonical work pages

  1. [1]

    nO i=1 X ai i Z bi i # ρ

    Note that before the encryption Client does not apply the evaluation scheme of the gates in order to create the initial state, so that the Init gate does not need to be compiled in the Clifford+ T gates of the universal set of gates G. After creating the initial state, Client initializes the classical bits that store the encrypting key at random, and use ...

    work page

  2. [2]

    Brakerski, C

    Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference , pages 309—-325, 2012

    work page 2012

  3. [3]

    C. Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009

    work page 2009

  4. [4]

    P. P. Rohde, J. F. Fitzsimons, and A. Gilchrist. Quantum walks with encrypted data. Physical Review Letters, 109:150501, 2012

    work page 2012

  5. [5]

    https://quantum-computing.ibm.com/

    IBM Quantum. https://quantum-computing.ibm.com/. 2021

    work page 2021

  6. [6]

    S. H. Tan, J. A. Kettlewell, Y. Ouyang, L. Chen, and J. F. Fitzsimons. A quantum approach to homomorphic encryption. Scientific Reports, 6:33467, 2016

    work page 2016

  7. [7]

    M. Liang. Symmetric quantum fully homomorphic encryption with perfect security. Quantum information processing , 12:3675–3687, 2013

    work page 2013

  8. [8]

    L. Yu, C. A. P´ erez-Delgado, and J. F. Fitzsimons. Limitations on information theoretically secure quantum homomorphic encryption. Physical Review A , 90:050303, 2014

    work page 2014

Show all 60 references
  1. [9]

    M. Liang. Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security. Quantum Information Processing, 19:28, 2020

    2020

  2. [10]

    M. Liang. Quantum fully homomorphic encryption scheme based on universal quantum circuit. Quantum Information Processing, 14:2749–2759, 2015

    2015

  3. [11]

    C. Y. Lai and K. M. Chung. On statistically-secure quantum homomorphic encryption. Quantum Information and Computation, 18:0785–0794, 2018

    2018

  4. [12]

    Einstein, B

    A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of physical reality be considered complete? Phys. Rev, 47:777–780, 1935

    1935

  5. [13]

    Broadbent and S

    A. Broadbent and S. Jeffery. Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity. In Advances in Cryptology – CRYPTO 2015 , pages 609–629, 2015

    2015

  6. [14]

    C. Gong, Z. Dong, A. Gani, and H. Qi. Quantum Ciphertext Dimension Reduction Scheme for Homomorphic Encrypted Data. In 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, pages 903–910, 2021

    2021

  7. [15]

    C. Gong, J. Du, Z. Dong, Z. Guo, A. Gani, L. Zhao, and H. Qi. Grover algorithm-based quantum homomorphic encryption ciphertext retrieval scheme in quantum cloud computing. Quantum Information Processing, 19:1–17, 2020

    2020

  8. [16]

    MADQuantum-CM

    The initial state of the walk is chosen as |ψ(0)⟩ = √ 0.75 |ψ0⟩ + √ 0.25 |ψ4⟩. This state is created with an RY gate that puts the first register in √ 0.75 |0⟩1 + √ 0.25 |4⟩1, and a posterior application of the update operator V . Note that since Client does not perform QHE ev...

    2026

  9. [17]

    Fern´ andez and M

    P. Fern´ andez and M. A. Martin-Delgado. Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm. Journal of Physics A: Mathematical and Theoretical , 57:365301, 2024

    2024

  10. [18]

    Ganjian, C

    S. Ganjian, C. Paddock, and A. Broadbent. Demonstrating Quantum Homomorphic Encryption Through Simulation. arXiv:2406.16247, 2024

    2024 arXiv

  11. [19]

    Yarter, G

    M. Yarter, G. Uehara, and A. Spanias. Implementation and analysis of quantum homomorphic encryption. In 2022 13th International Conference on Information, Intelligence, Systems and Applications (IISA). IEEE , pages 1–5, 2022

    2022

  12. [20]

    Fern´ andez and M

    P. Fern´ andez and M. A. Martin-Delgado. Implementing the Grover algorithm in homomorphic encryption schemes.Physical Review Research, 6:043109, 2024

    2024

  13. [21]

    Aharonov, L

    Y. Aharonov, L. Davidovich, and N. Zagury. Quantum random walks. Physical Review A , 48:1687, 1993

    1993

  14. [22]

    Farhi and S

    E. Farhi and S. Gutmann. Quantum computation and decision trees. Physical Review A , 58:915, 1998

    1998

  15. [23]

    Magniez, M

    F. Magniez, M. Santha, and M. Szegedy. Quantum Algorithms for the Triangle Problem. SIAM Journal on Computing , 37:413–424, 2007

    2007

  16. [24]

    Ambainis

    A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing , 37:210–239, 2007

    2007

  17. [25]

    Shenvi, J

    N. Shenvi, J. Kempe, and K. B. Whaley. Quantum random-walk search algorithm. Physical Review A , 67:052307, 2003

    2003

  18. [26]

    Portugal

    R. Portugal. Quantum Walks and Search Algorithms . New York: Springer, 2013

    2013

  19. [27]

    M. Szegedy. Quantum speed-up of Markov chain based algorithms. 45th Annual IEEE Symposium on Foundations of Computer Science, pages 32–41, 2004

    2004

  20. [28]

    L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing , 1996

    1996

  21. [29]

    Lemieux, B

    J. Lemieux, B. Heim, D. Poulin, K. Svore, and M. Troyer. Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm. Quantum, 4:287, 2020

    2020

  22. [30]

    P. A. M. Casares, R. Campos, and M. A. Martin-Delgado. QFold: Quantum Walks and Deep Learning to Solve Protein Folding. Quantum Science and Technology, 7:025013, 2022

    2022

  23. [31]

    Campos, P

    R. Campos, P. A. Casares, and M. A. Martin-Delgado. Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems. Quantum Machine Intelligence , 5:28, 2023

    2023

  24. [32]

    Escrig, R

    G. Escrig, R. Campos, P. A. Moreno Casares, and M. A. Martin-Delgado. Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm. Classical and Quantum Gravity , 40:045001, 2023

    2023

  25. [33]

    Escrig, R

    G. Escrig, R. Campos, H. Qi, and M. A. Martin-Delgado. Quantum Bayesian Inference with Renormalization for Gravi- tational Waves. The Astrophysical Journal Letters , 979:L36, 2025

    2025

  26. [34]

    G. D. Paparo and M. A. Martin-Delgado. Google in a Quantum Network. Scientific Reports, 2:444, 2012. 28

    2012

  27. [35]

    G. D. Paparo, M¨ uller M., F. Comellas, and M. A. Martin-Delgado. Quantum Google in a Complex Network. Scientific Reports, 3:2773, 2013

    2013

  28. [36]

    S. A. Ortega and M. A. Martin-Delgado. Generalized quantum PageRank algorithm with arbitrary phase rotations. Physical Review Research, 5:013061, 2023

    2023

  29. [37]

    Magniez, A

    F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via Quantum Walk. SIAM Journal on Computing , 40:142–164, 2011

    2011

  30. [38]

    H. Wang, J. Wu, X. Yang, P. Chen, and X. Yi. An Enhanced Quantum PageRank Algorithm Integrated with Quan- tum Search. 2014 Eighth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing , IEEE:74–81, 2014

    2014

  31. [39]

    R. A. Santos. Szegedy’s quantum walk with queries. Quantum Information Processing, 15:4461–4475, 2016

    2016

  32. [40]

    G. D. Paparo, V. Dunjko, A. Makmal, M. A. Martin-Delgado, and H. J. Briegel. Quantum Speedup for Active Learning Agents. Physical Review X , 4:031002, 2014

    2014

  33. [41]

    S. A. Ortega and M. A. Martin-Delgado. Complex-Phase Extensions of the Szegedy Quantum Walk on Graphs. Physical Review A, 111:032216, 2025

    2025

  34. [42]

    A Ortega and M

    S. A Ortega and M. A. Martin-Delgado. Discrete-time Semiclassical Szegedy Quantum Walks. Physica A , 625:129021, 2023

    2023

  35. [43]

    S. A. Ortega and M. A. Martin-Delgado. Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine. Physical Review Research, 6:043014, 2024

    2024

  36. [44]

    Torres, S

    J. Torres, S. A. Ortega, and M. A. Martin-Delgado. A Quantum Signature Validation Algorithm for Efficient Detection of Tampered Transactions in Blockchains. arXiv:2502.15023, 2025

    2025 arXiv

  37. [45]

    S. A. Ortega and M. A. Martin-Delgado. Squwals: A szegedy quantum walks simulator. Advanced Quantum Technologies, 7:2400022, 2024

    2024

  38. [46]

    P. O. Boykin and V. Roychowdhury. Optimal encryption of quantum bits. Physical Review A , 67:042317, 2003

    2003

  39. [47]

    M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010

    2010

  40. [48]

    A. Childs. Quantum algorithms: LECTURE 14. Discrete-time quantum walk. University of Waterloo , 2008

    2008

  41. [49]

    By quantum time we refer to a parameter that determines the duration of the quantum evolution, rather than a quantum operator

  42. [50]

    C. F. Chiang, D. Nagaj, and P. Wocjan. Efficient circuits for quantum walks. Quantum Information and Computation , 10:420–434, 2010

    2010

  43. [51]

    Loke and J

    T. Loke and J. B. Wang. Efficient quantum circuits for Szegedy quantum walks. Annals of Physics , 382:64–84, 2017

    2017

  44. [52]

    Hagberg, D

    A. Hagberg, D. S Chult, and P. Swart. Exploring network structure, dynamics, and function using networkx. In G. Varo- quaux, T. Vaught, and J. Millman, editors, Proceedings of the 7th Python in Science Conference , pages 11 – 15, Pasadena, CA USA, 2008

    2008

  45. [53]

    N. J. Ross and P. Selinger. Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Information and Computation, 16:901–953, 2016

    2016

  46. [54]

    See Supplementary Material for a proof of correctness for the update operator circuit of the bipartite graph, and also for the implementation of classical gates in Qiskit and further details about the simplified simulator

  47. [55]

    Javadi-Abhari el al

    A. Javadi-Abhari el al. Quantum computing with Qiskit. arXiv:2405.08810, 2024

    2024 arXiv

  48. [56]

    D. Maslov. Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Physical Review A , 93:022311, 2016

    2016

  49. [57]

    Zindorf and S

    B. Zindorf and S. Bose. Efficient Implementation of Multi-Controlled Quantum Gates. arXiv:2404.02279, 2024

    2024 arXiv

  50. [58]

    Galindo and M

    A. Galindo and M. A. Martin-Delgado. Information and computation: Classical and quantum aspects. Reviews of Modern Physics, 74:347, 2002

    2002

  51. [59]

    C. H. Bennett, G. Brassard, C. Cr´ epeau, R. Jozsa, A. Peres, and W. K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70:1895, 1993

    1993

  52. [60]

    U -rotated Bell basis

    R. Jozsa. An introduction to measurement based quantum computation. NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment , 199:137–158, 2006. Appendix A: Clifford+ T gates The usual Clifford gates used in this work a...

    2006

Pith tools

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