A Method for Constructing Quasi-Random Peaked Quantum Circuits

O.G. Udalov

REVIEW 4 major objections 5 minor 25 references

A Method for Constructing Quasi-Random Peaked Quantum Circuits

T0 review · 4 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read This paper proposes a scalable algorithm that builds random-looking brick-wall quantum circuits whose final measurement is, with high probability, a predetermined bitstring.

desk verdict The symmetry-breaking step that makes the whole method work is asserted but never described, so the paper is currently a plausible design sketch rather than a demonstrated algorithm; the underlying idea is worth a serious referee. read the letter →

arxiv 2508.07491 v1 pith:EAELGBXP submitted 2025-08-10 quant-ph cond-mat.mtrl-sci

O.G. Udalov This is my paper · ORCID

classification quant-phcond-mat.mtrl-sci

keywords quantumalgorithmpeakedcircuitbrick-wallmatrixproductstateadvantageverifiableBornmachinequasi-random

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

This paper proposes a method for constructing quasi-random "peaked" quantum circuits: circuits built from random two-qubit gates in a brick-wall layout whose final state is, with high probability, a predetermined computational basis string. The key move is to build the circuit as a random operator $\hat{Q}$, append its mirror inverse $\hat{Q}^{-1}$, then break the visible symmetry by replacing blocks in the mirror half with different-angle blocks that implement nearly the same two-qubit matrix. Because the replacement is done piece by piece rather than by one global optimization, the method scales to circuits beyond direct classical simulation. The peakedness is tunable through a deviation parameter $\delta$, and a variant produces circuits with two or more specified peak strings. If the construction holds at scale, it would provide a verifiable route to quantum advantage where the output is easy to check but hard to simulate.

What carries the argument

The unit of the construction is a two-qubit block $B$ made of six $U_3(\theta,\phi,\lambda)$ gates and two CZ gates, so the block is described by 18 rotation angles but acts as a $4\times 4$ unitary matrix $M$. The method's lever is the (asserted) non-uniqueness of angle sets: for a generic block $B(S_1)$ there is a distinct $S_2$ with $B(S_2)\approx B(S_1)$, so one can swap mirror-half blocks for different-angle versions that preserve the approximate inverse $\hat{Q}_1\approx\hat{Q}^{-1}$ while destroying the symmetry between the two halves. The deviation $\delta = \sqrt{\sum_{ij}(M^1_{ij}-M^2_{ij})^2/16}$ controls the trade-off: smaller $\delta$ preserves peakedness, larger $\delta$ hides

What would settle it

Run the full construction for a moderately large circuit, say $n_q=20$ qubits and $n_l=40$ layers, classically simulate it, and check whether the hidden string is the most frequent output with $P_{\rm peak}/P_{\rm second}\ge 10$ under the paper's tolerance $\delta$. If not, the claimed scalability fails. A more targeted check is to take a random block $B(S_1)$ and search for a distinct $S_2$ with $\delta$ below the threshold of Fig. 4(b); finding no such partner for typical blocks would falsify the core construction step.

Watch

Extended reading notes

Core claim

The central claim is that, for any chosen bitstring $x_{\rm hid}$, one can efficiently produce a random-looking brick-wall circuit whose output distribution concentrates on $x_{\rm hid}$, with the ratio $P_{\rm peak}/P_{\rm second}$ of the peak probability to the second most likely string controlled by the user. The construction starts from a random circuit $\hat{Q} = \prod_i B_i$ of two-qubit blocks, appends the reversed inverse operators to form a trivial peaked circuit with output $|00\ldots0\rangle$, then applies and commutes NOT gates through the circuit to conceal $x_{\rm hid}$. The critical step is modifying the mirror half to $\hat{Q}_1 \approx \hat{Q}^{-1}$ with the block symmetry $

Load-bearing premise

The load-bearing premise is that, for a generic two-qubit block, one can always find a different set of angles whose block matrix is close enough to the original that replacing mirror-half blocks breaks the circuit's symmetry without degrading the final probability peak below the chosen threshold; the paper asserts this multiplicity of angle sets without derivation.

Editorial extensions

If this is right

If the construction scales as claimed, peaked circuits can be built at sizes that defeat direct state-vector simulation, while the output stays easy to verify.
The symmetry-breaking replacement makes the hidden bitstring hard to recover by comparing the two halves of the circuit, addressing an obvious attack on the earlier construction.
Tuning $\delta$ gives an explicit knob for how sharply the output peaks, so experiments can choose a trade-off between verification ease and classical hardness.
The entangling-block insertion produces double- or multi-peaked circuits, i.e., quasi-random circuits whose output is a small set of specified strings, which could serve as bespoke sampling benchmarks.
MPS-based simulation remains useful for shallow peaked circuits but, for depths where quantum advantage would be claimed, the required bond dimension approaches its maximum, so MPS does not trivialize the verification.

Reading between the lines

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

Editorial extension: if the approximate-equivalence of angle sets is generic, the same piecewise-replacement trick could be used to compress or reshape any brick-wall circuit, not only peaked ones, by replacing subcircuits with alternative blocks while preserving the overall unitary.
Editorial extension: the method resembles a programmable Born machine without global parameter training; one could extend it to synthesize arbitrary sparse output distributions by chaining multiple entangling-block insertions, which the paper only sketches.
Editorial extension: a natural stress test, not reported in the paper, is to apply the construction well beyond the tested qubit counts and check whether the required $\delta_{\rm th}$ continues to stay flat with $n_q$; the paper's data cover only the sizes examined.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: there is a real idea here, but the manuscript as written does not let you verify it. The proposed trick is to take a random brick-wall circuit plus its exact inverse, then replace each block in the inverse half with a different-angle block that still implements nearly the same unitary. If that works, you get a peaked quasi-random circuit with no visible mirror symmetry, and the construction is local and scalable, unlike the global optimization in Aaronson and Zhang. That is a genuinely different approach. The NOT-gate hiding and multi-peaked extensions are also new relative to [7], and the MPS section is a useful sanity check. The GitHub link is a good sign, though I could not verify what it contains from the manuscript.

The soft spots are serious and central. Step 3 of the algorithm—the symmetry-breaking replacement—is asserted but never described. There is no procedure for selecting the replacement blocks, no bound on how the accumulated deviation degrades the peak, and no actual example of two angle sets giving nearly the same 4x4 block. The paper states that such redundancy exists because the block has 18 parameters, but that is not a proof, and a claim like this is easy to demonstrate with one example. The text also jumps from the building-block description directly to Fig. 4: Figs. 1–3, which are supposed to illustrate the three steps, do not appear in the version I read. That makes the central construction unreviewable as it stands.

The empirical claims are also thinner than the text implies. Peakedness is defined with an arbitrary Ppeak/Psecond = 10 threshold, the allowed deviation delta_th is calibrated numerically, and the 'several tens of qubits' projection is an extrapolation from small simulated sizes. None of these would be fatal if the core construction were fully specified, but together they mean the paper currently presents a plausible design sketch, not a demonstrated method.

The citation pattern is fine; the author builds on [7] and cites the relevant Bravyi-Gosset-Liu result for shallow circuits. No self-citation or secrecy problems.

I think the reader's REJECT is justified only in the sense that the paper cannot be accepted in this state. It is not obviously wrong. If the author supplies the missing step, figures, and an explicit redundancy example, this becomes a paper worth having. My recommendation: send it to peer review with a firm request for those additions. The referee should focus on Step 3 and the delta-to-peak relationship.

Referee Report

4 major / 5 minor

Summary. The paper proposes a scalable method for constructing quasi-random brick-wall circuits whose final measurement distribution is sharply peaked on a predetermined bitstring, with an optional extension to multiple peaks. The idea is to take a random circuit Q, append its inverse, then hide the target string via transformed NOT gates and break the mirror symmetry by replacing blocks of the inverse with approximately equivalent but differently parameterized blocks. The manuscript reports numerical simulations of peakedness versus circuit size and of MPS simulation threshold bond dimensions, concluding that the resulting deep peaked circuits are hard for MPS. It also sketches a circuit-size reduction procedure.

Significance. If the construction were fully specified and correct, the method could be a useful contribution to verifiable quantum advantage: it would provide a piecewise/scalable alternative to the global optimization in Aaronson-Zhang's peaked circuit sampling, and the negative MPS result would be relevant. The paper also provides code and studies a concrete simulation question. However, the present text does not yet contain the central algorithm, so the significance cannot be fully assessed.

major comments (4)

[Sec. 2] The paper announces a three-step algorithm and says 'Let us now consider each step in more detail', but after describing Step 1 (Sec. 2.1.1) the text jumps to Fig. 4. Sections 2.2 and 2.3 are absent. In particular, the core step — replacing the mirror half Q^{-1} by Q1 ≈ Q^{-1} with broken symmetry — is never specified: no procedure for selecting the modified blocks, no error bound on the accumulated deviation, and no connection between δ and the final Ppeak. The reader cannot reproduce the construction or verify the central claim. This is the major blocker.
[Sec. 2.1.1] The assertion that 'for any block B(S1) with matrix M1, there exists at least one block B(S2) with matrix M2 such that M1 ≈ M2' is stated without proof or example; the 'example ... shown in Fig. 1' is not present in the manuscript. Since this assertion underpins the symmetry-breaking replacement in Step 3, it needs a constructive demonstration (e.g., explicit angle sets and the achieved δ) or a reference.
[Sec. 3 / Fig. 4] The scalability conclusion ('may be effective for large quantum circuits ... with several tens of qubits') is extrapolated from data at small nq (apparently ≤ 14) and from a linear interpolation that predicts Ppeak vanishing around 40 qubits. The extrapolation is not justified, and the statement that δth 'depends only weakly on the number of qubits' is based on a small range. If the authors wish to claim scalability beyond classical simulation, they need either analytic bounds or larger numerical evidence.
[Sec. 6] The conclusion that MPS offers no significant advantage for deeper peaked circuits is based on simulations up to nq=8 (Fig. 9) and nq up to about 14 (Fig. 10). The saturation behavior of χth in shallow circuits is consistent with Ref. [25], but the claim about deep circuits is an extrapolation. In addition, the use of 10^5 sampling shots introduces statistical uncertainty that is not quantified; please provide error bars or exact probability computations for small sizes.

minor comments (5)

[General / Figures] The manuscript references Figures 1-3 (e.g., Fig. 1(a) and Fig. 3) but they do not appear in the provided text; only Figs. 4-10 are present. Please check the uploaded version and include all figures.
[Sec. 2, Eq. (1)] The operator notation (e.g., \hat Q = \prod_{i=1}^N B_i, and the definition of \tilde B_i) is garbled in the PDF. Please use a clean ordered-product notation and define the index ranges explicitly.
[Sec. 4] The double-peaked construction is demonstrated only for a specific entangling block. The statement that 'more complex entangling operators' can generate any desired pair of strings is not demonstrated; at minimum give the general construction.
[Sec. 5] The reduced-block optimization is described only at the level of 'angles are optimized'; no details of the cost function, optimization method, or resulting approximation errors are provided. As this is a utility for shrinking circuits, please specify.
[Sec. 6] The notation 2^{n_q/2} for the maximum bond dimension is ambiguous for odd n_q; define \chi_{\max} precisely. Also, reference [5] has an incomplete author list ('U., V.').

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction starts from an exact inverse and the peak probability is computed, not assumed.

full rationale

The derivation chain is self-contained in the relevant sense. The peaked circuit is built by (1) generating a random brick-wall Q, (2) appending its exact inverse Q^{-1} so the output is |0...0> by construction, and (3) proposing to replace the mirror half with an approximate inverse Q1 ≈ Q^{-1} that breaks the symmetry. The claimed peakedness is then an empirical property of the resulting circuit: Ppeak and Psecond are obtained by simulation/sampling, and the threshold Ppeak/Psecond = 10 is explicitly declared arbitrary. No load-bearing step equates the prediction with a fitted parameter or a self-citation. The 'control' through δ is a post-hoc empirical calibration, not a quantity defined as the output. The main weaknesses of the paper are evidentiary, not circular: Step 3 is never given as an explicit algorithm, and Sec. 2.1.1 asserts without proof that multiple angle sets produce nearly identical 4x4 matrices. Those omissions prevent verification of the central construction but do not make the argument reduce to itself. There are no self-citations by the author; Ref. [7] and Ref. [25] are external prior work. Therefore the circularity score is 0.

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

No new physical entities are introduced. The algorithm relies on empirical hyperparameters (delta_th and the peakedness threshold) and standard gate-set/MPS assumptions. The missing description of the core construction leaves the status of these assumptions unverified in the provided text.

free parameters (3)

delta_th (maximum deviation for peak classification) = varies with nq, nl; approx 0.015 for nl=128 (Fig. 4b)
Empirically chosen to keep Ppeak/Psecond=10; controls the tradeoff between peakedness and symmetry breaking.
Ppeak/Psecond threshold = 10
Arbitrarily chosen criterion to classify a circuit as peaked, stated in Sec. 3.
angles of reduced blocks B4red = optimized by numerical procedure (Sec. 5)
Fitted to approximate the original block matrix for circuit shrinking; essential for the size-reduction and 'resolving' claims.

assumptions (3)

domain assumption The gate set {U3, CZ} with brick-wall layout can generate arbitrary or uniformly random unitaries (Step 1).
Relies on standard universality of single-qubit rotations plus CZ, and on random circuits forming approximate unitary designs.
domain assumption For any two-qubit block B(S1) there exists another block B(S2) with nearly the same matrix but different angles.
Stated in Sec. 2.1.1 without proof; this is the basis for Step 3's symmetry breaking.
domain assumption MPS simulation with sufficiently large bond dimension accurately approximates the output distribution.
Standard MPS truncation assumption; used in Sec. 6 to identify the hidden string.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Method for Constructing Quasi-Random Peaked Quantum Circuits." pith.science (2026). https://pith.science/paper/EAELGBXP

@misc{pith2026250807491,
  author       = {Pith},
  title        = {Pith review of: A Method for Constructing Quasi-Random Peaked Quantum Circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EAELGBXP}},
  note         = {Machine review of arXiv:2508.07491}
}

read the original abstract

An algorithm is proposed for constructing quasi-random "peaked" quantum circuits, i.e., circuits whose final qubit state exhibits a high probability concentration on a specific computational basis state. These circuits consist of random gates arranged in a brick-wall architecture. While the multiqubit state in the middle of the circuit can exhibit significant entanglement, the final state is, with high probability, a predetermined pure bitstring. A technique is introduced to obscure the final bitstring in the structure of the quantum circuit. The algorithm allows precise control over the probability of the final peaked state. A modified version of the algorithm enables the construction of double- or multi-peaked quantum circuits. The matrix product state (MPS) method is evaluated for simulating such circuits; it performs effectively for shallow peaked circuits but offers no significant advantage for deeper ones.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 7 canonical work pages

[7]

arXiv (2404.14493) (2024)

Aaronson, S., Zhang, Y.: On verifiable quantum advantage with peaked circuit sampling. arXiv (2404.14493) (2024)

arXiv 2024
[25]

In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

Bravyi, S., Gosset, D., Liu, Y.: Classical simulation of peaked shallow quan- tum circuits. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024, pp. 561–572. Association for Computing Machin- ery, New York, NY, USA (2024). https://doi.org/10.1145/3618260.3649638 . �� 17

arXiv 2024
[1]

Nature 574, 505–510 (2019) https://doi.org/10.1038/s41586-019-1666-5

Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J., Barends, R., Biswas, R., Boixo, S., Brandao, F., Buell, D., Burkett, B., Chen, Y., Chen, Z., Chiaro, B., Collins, R., Courtney, W., Dunsworth, A., Farhi, E., Foxen, B., Martinis, J.: Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019) https://doi.org/10.1038/...

doi:10.1038/s41586-019-1666-5 2019
[2]

Computational Complexity Conference (CCC 2017), ser

Aaronson, S., Chen Geddes, L.: Complexity-theoretic foundations of quantum supremacy experiments. Computational Complexity Conference (CCC 2017), ser. LIPIcs 79, 1–67 (2017)

work page 2017
[3]

arXiv (1909.06210) (2019)

Movassagh, R.: Quantum supremacy and random circuits. arXiv (1909.06210) (2019)

arXiv 1909
[4]

arXiv (1203.5813) (2012)

Preskill, J.: Quantum computing and the entanglement frontier. arXiv (1203.5813) (2012)

arXiv 2012
[5]

arXiv (1803.04402) (2018)

Bouland, A., Fefferman, B., Nirkhe, C., U., V.: Quantum supremacy and the complexity of random circuit sampling. arXiv (1803.04402) (2018)

arXiv 2018
[6]

In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and fac- toring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134 (1994). https://doi.org/10.1109/SFCS.1994.365700

arXiv 1994

Show all 25 references

[8]

Liu, J.-G., Wang, L.: Differentiable learning of quantum circuit born machines. Phys. Rev. A 98, 062324 (2018) https://doi.org/10.1103/PhysRevA.98.062324

2018 doi
[9]

npj Quantum Information 5, 45 (2019) https: //doi.org/10.1038/s41534-019-0157-8

Benedetti, M., Garcia-Pintos, D., Perdomo, O., Leyton-Ortega, V., Nam, Y., Perdomo-Ortiz, A.: A generative modeling approach for benchmarking and train- ing shallow quantum circuits. npj Quantum Information 5, 45 (2019) https: //doi.org/10.1038/s41534-019-0157-8

2019 doi
[10]

arXiv preprint arXiv:2205.04730 (2022)

Du, Y., Tu, Z., Wu, B., Yuan, X., Tao, D.: Power of quantum generative learning. arXiv preprint arXiv:2205.04730 (2022)

2022 arXiv
[11]

Quantum Science and Technology 6(2), 024013 (2021) https://doi.org/10.1088/2058-9565/abd2db

Coyle, B., Henderson, M., Le, J.C.J., Kumar, N., Paini, M., Kashefi, E.: Quantum versus classical generative modelling in finance. Quantum Science and Technology 6(2), 024013 (2021) https://doi.org/10.1088/2058-9565/abd2db

2021 doi
[12]

Physical Review A 94(2), 022309 (2016) https://doi.org/10.1103/PhysRevA.94.022309

Wecker, D., Hastings, M.B., Troyer, M.: Training a quantum optimizer. Physical Review A 94(2), 022309 (2016) https://doi.org/10.1103/PhysRevA.94.022309

2016 doi
[13]

arXiv preprint 15 arXiv:2311.12929 (2023) https://doi.org/10.48550/arXiv.2311.12929

Gharibyan, H., Su, V., Tepanyan, H.: Hierarchical learning for quantum ml: Novel training technique for large-scale variational quantum circuits. arXiv preprint 15 arXiv:2311.12929 (2023) https://doi.org/10.48550/arXiv.2311.12929

2023 doi arXiv
[14]

Berthusen, N.F., Trevisan, T.V., Iadecola, T., Orth, P.P.: Quantum dynam- ics simulations beyond the coherence time on noisy intermediate-scale quantum hardware by variational trotter compression. Phys. Rev. Res. 4, 023097 (2022) https://doi.org/10.1103/PhysRevResearch.4.023097

2022 doi
[15]

Scientific Reports 15, 15746 (2025) https://doi.org/10.1038/s41598-025-00151-x

Mih´ alikov´ a, I., Krejˇ c ´ ı, M., Fri´ ak, M.: The impact of quantum circuit archi- tecture and hyperparameters on variational quantum algorithms exemplified in the electronic structure of the gaas crystal. Scientific Reports 15, 15746 (2025) https://doi.org/10.1038/s41598-...

2025 doi
[16]

Uvarov, A.V., Kardashin, A.S., Biamonte, J.D.: Machine learning phase tran- sitions with a quantum processor. Phys. Rev. A 102, 012415 (2020) https: //doi.org/10.1103/PhysRevA.102.012415

2020 doi
[17]

Journal of Optics B: Quantum and Semiclassical Optics 7(10), 347–352 (2005) https://doi.org/10.1088/1464-4266/7/10/021

Emerson, J., Alicki, R., ˙Zyczkowski, K.: Scalable noise estimation with random unitary operators. Journal of Optics B: Quantum and Semiclassical Optics 7(10), 347–352 (2005) https://doi.org/10.1088/1464-4266/7/10/021

2005 doi
[18]

Nature Reviews Physics5, 9–24 (2023) https://doi.org/10.1038/s42254-022-00535-2

Elben, A., Flammia, S.T., Huang, H.-Y., Kueng, R., Preskill, J., Vermersch, B., Zoller, P.: The randomized measurement toolbox. Nature Reviews Physics5, 9–24 (2023) https://doi.org/10.1038/s42254-022-00535-2

2023 doi
[19]

arXiv preprint arXiv:2405.08810 (2024) https://doi.org/10.48550/arXiv.2405.08810 arXiv:2405.08810

Javadi-Abhari, A., Treinish, M., Krsulich, K., Wood, C.J., Lishman, J., Gacon, J., Martiel, S., Nation, P.D., Bishop, L.S., Cross, A.W., Johnson, B.R., Gambetta, J.M.: Quantum computing with qiskit. arXiv preprint arXiv:2405.08810 (2024) https://doi.org/10.48550/arXiv.2405.088...

2024 doi arXiv
[20]

arXiv preprint arXiv:2302.08880 (2023) https: //doi.org/10.48550/arXiv.2302.08880 arXiv:2302.08880

Xu, X., Benjamin, S., Sun, J., Yuan, X., Zhang, P.: A herculean task: Classical simulation of quantum computers. arXiv preprint arXiv:2302.08880 (2023) https: //doi.org/10.48550/arXiv.2302.08880 arXiv:2302.08880

2023 doi arXiv
[21]

Ba˜ nuls, M.C., Or´ us, R., Latorre, J.I., P´ erez, A., Ruiz-Femen ´ ıa, P.: Simulation of many-qubit quantum computation with matrix product states. Phys. Rev. A 73, 022344 (2006) https://doi.org/10.1103/PhysRevA.73.022344

2006 doi
[22]

ArXiv (2007) https://doi.org/10.48550/arXiv.quant-ph/0608197 [quant-ph]

Perez-Garcia, D., Verstraete, F., Wolf, M.M., Cirac, J.I.: Matrix product state representations. ArXiv (2007) https://doi.org/10.48550/arXiv.quant-ph/0608197 [quant-ph]

2007 doi arXiv
[23]

Physical Review A 109(6), 062437 (2024) https://doi.org/10.1103/PhysRevA.109.062437 arXiv:2305.19231 [quant-ph]

Martin, A., Ayral, T., Jamet, F., Ranˇ ci´ c, M.J., Simon, P.: Combining matrix product states and noisy quantum computers for quantum simulation. Physical Review A 109(6), 062437 (2024) https://doi.org/10.1103/PhysRevA.109.062437 arXiv:2305.19231 [quant-ph]

2024
[24]

Patra, S., Jahromi, S.S., Singh, S., Orus, R.: Efficient tensor network simulation 16 of ibm’s largest quantum processors. Phys. Rev. Res. 6, 013326 (2024) https: //doi.org/10.1103/PhysRevResearch.6.013326

2024 doi

Pith tools

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

[1] [7]

arXiv (2404.14493) (2024)

Aaronson, S., Zhang, Y.: On verifiable quantum advantage with peaked circuit sampling. arXiv (2404.14493) (2024)

arXiv 2024

[2] [25]

In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

Bravyi, S., Gosset, D., Liu, Y.: Classical simulation of peaked shallow quan- tum circuits. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024, pp. 561–572. Association for Computing Machin- ery, New York, NY, USA (2024). https://doi.org/10.1145/3618260.3649638 . �� 17

arXiv 2024

[3] [1]

Nature 574, 505–510 (2019) https://doi.org/10.1038/s41586-019-1666-5

Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J., Barends, R., Biswas, R., Boixo, S., Brandao, F., Buell, D., Burkett, B., Chen, Y., Chen, Z., Chiaro, B., Collins, R., Courtney, W., Dunsworth, A., Farhi, E., Foxen, B., Martinis, J.: Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019) https://doi.org/10.1038/...

doi:10.1038/s41586-019-1666-5 2019

[4] [2]

Computational Complexity Conference (CCC 2017), ser

Aaronson, S., Chen Geddes, L.: Complexity-theoretic foundations of quantum supremacy experiments. Computational Complexity Conference (CCC 2017), ser. LIPIcs 79, 1–67 (2017)

work page 2017

[5] [3]

arXiv (1909.06210) (2019)

Movassagh, R.: Quantum supremacy and random circuits. arXiv (1909.06210) (2019)

arXiv 1909

[6] [4]

arXiv (1203.5813) (2012)

Preskill, J.: Quantum computing and the entanglement frontier. arXiv (1203.5813) (2012)

arXiv 2012

[7] [5]

arXiv (1803.04402) (2018)

Bouland, A., Fefferman, B., Nirkhe, C., U., V.: Quantum supremacy and the complexity of random circuit sampling. arXiv (1803.04402) (2018)

arXiv 2018

[8] [6]

In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and fac- toring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134 (1994). https://doi.org/10.1109/SFCS.1994.365700

arXiv 1994