pith. sign in

arxiv: 2606.00222 · v1 · pith:6BQWHJWLnew · submitted 2026-05-29 · 🪐 quant-ph

How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures

Alice Barthe This is my paper

Pith reviewed 2026-06-28 22:06 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum oraclespseudorandom materialstextured materialsgeometry queriesquantum circuitslinear systems simulationGrover boundsmaterial microstructures
0
0 comments X

The pith

Imposing suitable local structure on pseudorandom textured materials allows their geometry oracles to be realized with polynomial-size quantum circuits.

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

The paper studies when oracles for the geometry of complex materials can be implemented efficiently by quantum circuits rather than treated as black boxes. Without extra structure, materials with exponentially many geometric features lead to oracles that are intractable because of Grover-type search lower bounds. When a specific pseudorandom local structure is added, a broad family of such materials admits explicit polynomial-size circuit constructions for the oracle. These constructions are given and checked via numerical simulation. A reader would care because quantum algorithms for linear systems and material simulation routinely assume such oracles exist.

Core claim

When suitable structure is imposed, a broad family of pseudorandom locally textured materials with exponentially many geometric features admits geometry oracles that can be queried through polynomial-size quantum circuits; explicit circuit constructions are provided and their behavior is verified through numerical simulation, in contrast to the general case where Grover-type lower bounds make the oracles intractable.

What carries the argument

The imposed pseudorandom local structure on the textured materials, which reduces geometry queries to polynomial-size quantum circuits.

If this is right

  • Quantum linear-systems algorithms become applicable to these rule-described materials once the oracles are realized by small circuits.
  • Rule-based material descriptions shift from intractable to tractable for quantum simulation when the pseudorandom structure is present.
  • The explicit circuits supply a direct method to embed the material geometry into larger quantum algorithms.
  • Numerical verification establishes that the circuits correctly reproduce the intended local texture queries on the tested instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar local-structure conditions might render other physics oracles efficient in quantum algorithms beyond linear systems.
  • One could design families of microstructures that deliberately satisfy the structure to enable quantum simulation experiments.
  • Variations of the local rules could be tested to see whether even smaller circuits or additional query types become possible.

Load-bearing premise

The materials must possess the specific pseudorandom local structure that permits the polynomial-size circuit constructions.

What would settle it

A concrete material obeying the stated pseudorandom local structure for which every quantum circuit implementing the geometry oracle requires superpolynomial size, or a numerical simulation in which the proposed circuit fails to return the correct geometry query outcome.

Figures

Figures reproduced from arXiv: 2606.00222 by Alice Barthe.

Figure 1
Figure 1. Figure 1: Quantum circuit for a single round of SPECK [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Quantum circuit flagging M random centres. x is the input register, copied into the register y. The pseudorandom permutation P (k) made of multiple rounds of [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of hole shape on a 3 × 3 grid, with the centre pixel corresponding to the [0, 0] coordinate. The corresponding set of T = 4 offsets δ, represented as black pixels, is ∆ = {[0, 0], [−1, 0], [0, −1], [0, 1]}. Given the random-centre map ck of Equa￾tion (3.13), we define the associated fixed-shape hole geometry by h∆,k(x) = 1[∃δ ∈ ∆, ck(x − δ) = 1] . (3.16) A site is hollow if, after subtracting one o… view at source ↗
Figure 4
Figure 4. Figure 4: Quantum circuit for the fixed-shape hole oracle, [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A realisation of quantum cheese: For a quan [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Quantum circuit to apply a convolution with [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Different textures obtained from geometries [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Differential metric R for different number input size 2n and number of rounds m. Because the benchmark is inherently random as it samples random bit-string, we show the average as a continuous line, and individual benchmark instance results as points to get a sense of the distribution. C Randomness of SPECK We propose the standard differential metric to assess whether a function is random enough. It is com… view at source ↗
read the original abstract

Quantum algorithms for simulating linear systems are often formulated under oracle access assumptions. A central question is when such oracles can be implemented by polynomial-size quantum circuits. In this paper, we study this question for materials specified by rules rather than by exhaustive descriptions. We focus on textured materials with exponentially many geometric features. In two settings, we show that, without additional structure, describing such geometries yields Grover-type lower bounds, making the corresponding quantum oracles intractable in general. In contrast, when suitable structure is imposed, we identify a broad family of pseudorandom locally textured materials whose geometry can be queried through a polynomial-size quantum circuit. We provide explicit circuit constructions for these oracles and verify their behaviour through numerical simulation.

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.

Referee Report

2 major / 1 minor

Summary. The paper claims that quantum oracles for geometry queries on materials with exponentially many pseudorandom features are intractable in general due to Grover-type lower bounds, but that imposing suitable local pseudorandom structure permits explicit constructions of polynomial-size quantum circuits realizing these oracles, with behavior verified by numerical simulation.

Significance. If the explicit constructions are polynomial in the description length (log of the number of microstructures) and the numerical evidence supports the scaling, the result would allow oracle-based quantum linear-systems algorithms to be instantiated for a broad class of structured complex materials without incurring exponential circuit costs, addressing a key gap between abstract oracle models and concrete circuit implementations.

major comments (2)
  1. [§3, §4] The central claim requires that the circuit family size is polynomial in the description length rather than in N. §3 (explicit constructions) and §4 (numerical verification): the simulations are performed only on finite small instances; it is not shown that gate count or depth remains O(poly(log N)) rather than acquiring a hidden exponential dependence once the number of microstructures becomes exponential, which is the load-bearing distinction given the Grover lower bound for the unstructured case.
  2. [§2] The definition of the imposed pseudorandom local structure must be shown to be independent of N. If the structure is defined via a family whose description length itself grows with log N in a way that encodes the geometry, the polynomial-size claim reduces by construction; this needs explicit verification against the lower-bound argument.
minor comments (1)
  1. [Abstract] The abstract states 'verify their behaviour through numerical simulation' but provides no details on the metrics (e.g., fidelity, gate count scaling) or the range of instance sizes tested.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed review and valuable comments on our manuscript. We address each of the major comments below.

read point-by-point responses

  1. Referee: [§3, §4] The central claim requires that the circuit family size is polynomial in the description length rather than in N. §3 (explicit constructions) and §4 (numerical verification): the simulations are performed only on finite small instances; it is not shown that gate count or depth remains O(poly(log N)) rather than acquiring a hidden exponential dependence once the number of microstructures becomes exponential, which is the load-bearing distinction given the Grover lower bound for the unstructured case.

    Authors: The explicit constructions in §3 are given analytically in terms of the description length of the pseudorandom structure, which is O(log N), and establish polynomial circuit size without hidden exponential factors. The numerical simulations in §4 are for verification on small instances only and do not constitute the proof of scaling. We will revise §3 and §4 to include an explicit statement of the asymptotic gate count in terms of the description length to make this distinction clearer. revision: yes

  2. Referee: [§2] The definition of the imposed pseudorandom local structure must be shown to be independent of N. If the structure is defined via a family whose description length itself grows with log N in a way that encodes the geometry, the polynomial-size claim reduces by construction; this needs explicit verification against the lower-bound argument.

    Authors: The local pseudorandom structure is defined by a fixed family of local rules with description length independent of N; the rules do not encode the global geometry but only local texture properties that apply uniformly. This is distinct from the unstructured case where the full exponential description is required. We will add a paragraph in §2 explicitly comparing the description length to the Grover lower bound argument to verify independence from N. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The provided abstract and context describe a claim of explicit circuit constructions for oracles under imposed pseudorandom local structure, verified by numerical simulation. No equations, self-definitions, fitted parameters renamed as predictions, or self-citation chains are exhibited that would reduce any derivation to its inputs by construction. The central claim relies on the imposed structure enabling polynomial-size circuits, which is presented as an independent identification rather than a tautology. This is a standard non-finding for a paper whose derivation chain is not shown to collapse.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no extractable free parameters, axioms, or invented entities.

pith-pipeline@v0.9.1-grok · 5641 in / 972 out tokens · 21998 ms · 2026-06-28T22:06:53.490397+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 31 canonical work pages · 1 internal anchor

  1. [1]

    Quantum algorithms for linear and non-linear fractional reaction-diffusion equations

    Dong An and Konstantina Trivisa. “Quantum algorithms for linear and non-linear fractional reaction-diffusion equations”. In:arXiv(2023).doi: 10.48550/arxiv.2310.18900. eprint: 2310.18900

    work page doi:10.48550/arxiv.2310.18900 2023

  2. [2]

    Progress in Cryptology – INDOCRYPT 2020, 21st International Conference on Cryptology in India, Banga- lore, India, December 13–16, 2020, Proceed- ings

    Ravi Anand, Arpita Maitra, and Sourav Mukhopadhyay. “Progress in Cryptology – INDOCRYPT 2020, 21st International Conference on Cryptology in India, Banga- lore, India, December 13–16, 2020, Proceed- ings”. In:Lecture Notes in Computer Sci- ence(2020), pp. 395–413.issn: 0302-9743. doi: 10.1007/978-3-030-65277-7˙18

    work page doi:10.1007/978-3-030-65277-7 2020

  3. [3]

    Quantum lower bounds by polynomials

    Robert Beals et al. “Quantum lower bounds by polynomials”. In:Journal of the ACM (JACM)48.4 (2001), pp. 778–797.issn: 0004-5411.doi: 10.1145/502090.502097

    work page doi:10.1145/502090.502097 2001

  4. [4]

    Ray Beaulieu et al.The SIMON and SPECK Families of Lightweight Block Ci- phers.url: https://eprint.iacr.org/ 2013/404

    2013

  5. [5]

    Effect of porosity and pore size distribution on elastic modulus of foams

    Simone De Carolis et al. “Effect of porosity and pore size distribution on elastic modulus of foams”. In:Interna- tional Journal of Mechanical Sciences261 (2024), p. 108661.issn: 0020-7403.doi: 10.1016/j.ijmecsci.2023.108661

    work page doi:10.1016/j.ijmecsci.2023.108661 2024

  6. [6]

    Non-equilibrium view of the amorphous so- lidification of liquids with competing in- teractions

    Ana Gabriela Carretas-Talamante et al. “Non-equilibrium view of the amorphous so- lidification of liquids with competing in- teractions”. In:The Journal of Chemical Physics158.6 (2023), p. 064506.issn: 0021- 9606.doi: 10.1063/5.0132525. eprint: 2302. 04290

    work page doi:10.1063/5.0132525 2023

  7. [7]

    & Schuch, N

    Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander. “High-precision quantum algo- rithms for partial differential equations”. In: Quantum5 (2021), p. 574.doi: 10.22331/q- 2021-11-10-574. eprint:2002.07868. 11

    work page doi:10.22331/q- 2021

  8. [9]

    A Classical-Quantum Adder with Constant Workspace and Linear Gates

    Craig Gidney. “A Classical-Quantum Adder with Constant Workspace and Linear Gates”. In:arXiv(2025).doi: 10.48550/arxiv.2507.23079. eprint: 2507 . 23079

    work page doi:10.48550/arxiv.2507.23079 2025

  9. [10]

    Halving the cost of quantum addition

    Craig Gidney. “Halving the cost of quantum addition”. In:Quantum2 (2018), p. 74.doi: 10.22331/q-2018-06-18-74. eprint: 1709.06 648

    work page doi:10.22331/q-2018-06-18-74 2018

  10. [11]

    Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en et al. “Quantum singu- lar value transformation and beyond: ex- ponential improvements for quantum ma- trix arithmetics”. In:Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing(2019), pp. 193– 204.doi: 10.1145/3313276.3316366. eprint: 1806.01838

    work page doi:10.1145/3313276.3316366 2019

  11. [12]

    Knill,Fault-tolerant postselected quantum computation: Schemes,arXiv [quant-ph] (2004), 10.48550/arXiv.quant- ph/0402171, quant-ph/0402171 [quant-ph]

    Lov K Grover. “A fast quantum mechan- ical algorithm for database search”. In: arXiv(1996).doi: 10.48550/arxiv.quant- ph/9605043. eprint:quant-ph/9605043

    work page doi:10.48550/arxiv.quant- 1996

  12. [13]

    Li Intercalation into Graphite: Direct Optical Imaging and Cahn–Hilliard Reaction Dynamics

    Yinsheng Guo et al. “Li Intercalation into Graphite: Direct Optical Imaging and Cahn–Hilliard Reaction Dynamics”. In:The Journal of Physical Chemistry Letters7.11 (2016), pp. 2151–2156.issn: 1948-7185.doi: 10.1021/acs.jpclett.6b00625

    work page doi:10.1021/acs.jpclett.6b00625 2016

  13. [14]

    Quantum algorithm for solving linear systems of equations

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum Algorithm for Linear Systems of Equations”. In:Physical Review Letters103.15 (2009), p. 150502.issn: 0031- 9007.doi: 10.1103/physrevlett.103.150502. eprint:0811.3171

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.103.150502 2009

  14. [15]

    Statistical scaling of geometric characteristics in stochastically generated pore microstructures

    Jeffrey D. Hyman, Alberto Guadagnini, and C. Larrabee Winter. “Statistical scaling of geometric characteristics in stochastically generated pore microstructures”. In:Com- putational Geosciences19.4 (2015), pp. 845– 854.issn: 1420-0597.doi: 10.1007/s10596- 015-9493-8

    work page doi:10.1007/s10596- 2015

  15. [16]

    Stochastic generation of explicit pore structures by thresholding Gaussian ran- dom fields

    Jeffrey D. Hyman and C. Larrabee Win- ter. “Stochastic generation of explicit pore structures by thresholding Gaussian ran- dom fields”. In:Journal of Computational Physics277 (2014), pp. 16–31.issn: 0021- 9991.doi: 10.1016/j.jcp.2014.07.046

    work page doi:10.1016/j.jcp.2014.07.046 2014

  16. [17]

    Simulating non- trivial incompressible flows with a quantum lattice Boltzmann algorithm

    David Jennings et al. “Simulating non- trivial incompressible flows with a quantum lattice Boltzmann algorithm”. In:arXiv (2025).doi: 10.48550/arxiv.2512.05781. eprint:2512.05781

    work page doi:10.48550/arxiv.2512.05781 2025

  17. [18]

    Random generation of combinatorial structures from a uniform distribution

    Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. “Random generation of combinatorial structures from a uniform distribution”. In:Theoretical Computer Sci- ence43 (1986), pp. 169–188.issn: 0304-3975. doi: 10.1016/0304-3975(86)90174-x

    work page doi:10.1016/0304-3975(86)90174-x 1986

  18. [19]

    Cloaking the underly- ing long-range order of randomly per- turbed lattices

    Michael A. Klatt, Jaeuk Kim, and Sal- vatore Torquato. “Cloaking the underly- ing long-range order of randomly per- turbed lattices”. In:Physical Review E 101.3 (2020), p. 032118.issn: 2470-0045. doi: 10.1103/physreve.101.032118. eprint: 2001.08161

    work page doi:10.1103/physreve.101.032118 2020

  19. [20]

    Reaction-Diffusion Model as a Framework for Understanding Biological Pattern Formation

    Shigeru Kondo and Takashi Miura. “Reaction-Diffusion Model as a Framework for Understanding Biological Pattern Formation”. In:Science329.5999 (2010), pp. 1616–1620.issn: 0036-8075.doi: 10.1126/science.1179047

    work page doi:10.1126/science.1179047 2010

  20. [21]

    Two Quantum Algo- rithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approxima- tion Method

    Manish Kumar. “Two Quantum Algo- rithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approxima- tion Method”. In:arXiv(2025).doi: 10.48550/arxiv.2510.19855. eprint: 2510 . 19855

    work page doi:10.48550/arxiv.2510.19855 2025

  21. [22]

    Colloidal systems with a short-range attraction and long- range repulsion: Phase diagrams, structures, and dynamics

    Yun Liu and Yuyin Xi. “Colloidal systems with a short-range attraction and long- range repulsion: Phase diagrams, structures, and dynamics”. In:Current Opinion in Col- loid & Interface Science39.Curr Opin Chem Eng 16 2017 (2019), pp. 123–136.issn: 1359- 0294.doi: 10.1016/j.cocis.2019.01.016

    work page doi:10.1016/j.cocis.2019.01.016 2017

  22. [23]

    Quantum Algo- rithm for Subcellular Multiscale Reaction- Diffusion Systems

    Margot Lockwood et al. “Quantum Algo- rithm for Subcellular Multiscale Reaction- Diffusion Systems”. In:arXiv(2025).doi: 10.48550/arxiv.2509.20668. eprint: 2509 . 20668

    work page doi:10.48550/arxiv.2509.20668 2025

  23. [24]

    How to Construct Pseudorandom Permutations from Pseudorandom Functions

    Michael Luby and Charles Rackoff. “How to Construct Pseudorandom Permutations from Pseudorandom Functions”. In:SIAM Journal on Computing17.2 (1988), pp. 373– 386.issn: 0097-5397.doi: 10.1137/0217022. 12

    work page doi:10.1137/0217022 1988

  24. [25]

    Quantum algorithms and the finite element method

    Ashley Montanaro and Sam Pallister. “Quantum algorithms and the finite ele- ment method”. In:Physical Review A93.3 (2016), p. 032324.issn: 2469-9926.doi: 10.1103/physreva.93.032324. eprint: 1512. 05903

    work page doi:10.1103/physreva.93.032324 2016

  25. [26]

    Pattern Formation in Precipitation Reactions: The Liesegang Phenomenon

    Hideki Nabika, Masaki Itatani, and Istvan Lagzi. “Pattern Formation in Precipitation Reactions: The Liesegang Phenomenon”. In:Langmuir36.2 (2020), pp. 481–497.issn: 0743-7463.doi: 10.1021/acs.langmuir.9b03018

    work page doi:10.1021/acs.langmuir.9b03018 2020

  26. [27]

    Equi- librium morphology of block copolymer melts

    Takao Ohta and Kyozi Kawasaki. “Equi- librium morphology of block copolymer melts”. In:Macromolecules19.10 (1986), pp. 2621–2632.issn: 0024-9297.doi: 10.1021/ma00164a028

    work page doi:10.1021/ma00164a028 1986

  27. [28]

    Effect of dis- order on the optical properties of col- loidal crystals

    Rajesh Rengarajan et al. “Effect of dis- order on the optical properties of col- loidal crystals”. In:Physical Review E71.1 (2005), p. 016615.issn: 1539-3755.doi: 10.1103/physreve.71.016615

    work page doi:10.1103/physreve.71.016615 2005

  28. [29]

    Elastic moduli of model random three-dimensional closed-cell cellular solids

    A.P. Roberts and E.J. Garboczi. “Elastic moduli of model random three-dimensional closed-cell cellular solids”. In:Acta Mate- rialia49.2 (2001), pp. 189–197.issn: 1359- 6454.doi: 10.1016/s1359-6454(00)00314-1

    work page doi:10.1016/s1359-6454(00)00314-1 2001

  29. [30]

    Elastic Properties of Model Porous Ceramics

    Anthony P. Roberts and Edward J. Gar- boczi. “Elastic Properties of Model Porous Ceramics”. In:Journal of the American Ceramic Society83.12 (2000), pp. 3041– 3048.issn: 0002-7820.doi: 10.1111/j.1151- 2916.2000.tb01680.x

    work page doi:10.1111/j.1151- 2000

  30. [31]

    Arbitrary Boundary Conditions and Constraints in Quantum Algorithms for Differential Equations via Penalty Projections

    Philipp Schleich et al. “Arbitrary Boundary Conditions and Constraints in Quantum Algorithms for Differential Equations via Penalty Projections”. In:arXiv(2025).doi: 10.48550/arxiv.2506.21751. eprint: 2506.2 1751

    work page doi:10.48550/arxiv.2506.21751 2025

  31. [32]

    Modeling and Fitting of Three-Dimensional Mineral Microstructures by Multinary Random Fields

    Jakob Teichmann et al. “Modeling and Fitting of Three-Dimensional Mineral Microstructures by Multinary Random Fields”. In:Mathematical Geosciences53.5 (2021), pp. 877–904.issn: 1874-8961.doi: 10.1007/s11004-020-09871-4

    work page doi:10.1007/s11004-020-09871-4 2021

  32. [33]

    An improved QFT-based quantum comparator and extended modular arithmetic using one ancilla qubit

    Yewei Yuan et al. “An improved QFT-based quantum comparator and extended modular arithmetic using one ancilla qubit”. In:New Journal of Physics25.10 (2023), p. 103011. doi: 10.1088/1367-2630/acfd52. 13 A Detailed circuit costs A.1 Primitives All costs are given forqqubits. •Copy.qCNOT gates. •Quantum-quantum addition.1ancilla qubit,2q−3Toffoli gates, and5...

    work page doi:10.1088/1367-2630/acfd52 2023

  33. [34]

    the exact value oracle ODφ :|x⟩|0n+1⟩↦−→|x⟩ ⏐⏐bin(2n+1dx) ⟩ , or

  34. [35]

    the exact time-evolution oracle Uφ:=e 2πiDφ . Then there is a polynomial-time quantum algorithm that, on inputφ, •outputs a special symbol⊥ifφis unsatisfiable, and •otherwise samples a satisfying assignment from a distributionµ φsatisfying ∥µφ−Unif(Sat(φ))∥TV≤2−n−2. 19 In particular, by the Jerrum–Valiant–Vazirani reduction from almost-uniform generation ...

  35. [36]

    prepare the Hadamard-test stateA|k⟩|0⟩|0n⟩,

  36. [37]

    estimate the eigenphase ofQinto registerP,

  37. [38]

    compute ˜θfrom the phase estimate,

  38. [39]

    compare ˜θwithθ⋆and write1[a k <0]into the output qubit,

  39. [40]

    uncompute the arithmetic workspace and the phase-estimation register,

  40. [41]

    The complete oracle can be expressed as ˜Va =A†PEm(Q)†R†CRPE m(Q)A,(F.33) wherePE m(Q)denotes the phase-estimation unitary forQ

    applyA †to restore the ancilla and work registers to|0⟩|0n⟩. The complete oracle can be expressed as ˜Va =A†PEm(Q)†R†CRPE m(Q)A,(F.33) wherePE m(Q)denotes the phase-estimation unitary forQ. Acting on the initial state, |k⟩i|0⟩h|0n⟩w|0m⟩p|0⟩o,(F.34) Thus, up to the bounded error of phase estimation, ˜Va|k⟩|0⟩|0n⟩|0m⟩|0⟩=|k⟩|0⟩|0n⟩|0m⟩|1[ak <0]⟩.(F.35) The ...