IP Library › Granted Patent US 12,493,813
Granted Patent B1
US 12,493,813 · App. 18/064,906 · Granted Dec 9, 2025

Distillation tile layouts and scheduling within a magic state factory for magic state distillation techniques

Inventors: Christopher Chamberland (Pasadena, CA); Prithviraj Prabhu (Los Angeles, CA)
Assignee: Amazon Technologies, Inc.
G06N10/60G06F9/5027
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,493,813
App. No.
18/064,906
Filed
Dec 12, 2022
Granted
Dec 9, 2025
Kind
B1
Art Unit
2111
USPC
714/746
Abstract

Techniques for optimizing distillation tile layouts for distillation tiles in a magic state factory of a quantum computer and a scheduling of distilled magic state production (e.g., using temporally encoded lattice surgery based (TELS-based) magic state distillation) using said distillation tiles are disclosed. Customized designs for distillation tile layouts that reduce space-time costs when executing a given quantum algorithm are presented, wherein the designs may be customized based, at least in part, on a selected classical error-correcting code and distillation circuit, on a decision whether to perform parallelized TELS-based magic state distillation, etc. Production of distilled magic states may then be configured using a round robin scheduling design in order to minimize potential time in which a processing core of the quantum computer is waiting for another newly distilled magic state from the magic state factory to use for logical computation related to the given quantum algorithm being executed.

Claims (55)

1 . A system, comprising:

one or more quantum hardware devices configured to implement a quantum computer that uses topological quantum codes, wherein the quantum computer comprises:

a processing core configured to execute a quantum algorithm; and

a magic state factory comprising distillation tiles, implemented via rectangular patches of the topological quantum codes, wherein the magic state factory is configured to generate distilled magic states in respective distillation tiles to be used during execution of the quantum algorithm; and

one or more computing devices configured to cause the one or more quantum hardware devices to generate the distilled magic states for execution of the quantum algorithm, wherein, to generate the distilled magic states, the one or more computing devices are further configured to:

determine a layout for the distillation tiles such that a first boundary of respective rectangular patch boundaries is accessible, via a routing space, by the processing core, wherein the first boundary is a shorter boundary of the respective rectangular patch boundaries; and

determine a round robin scheduling to generate the distilled magic states such that a first moment in time at which a given one of the distillation tiles has generated one or more distilled magic states of the distilled magic states is offset from a second moment in time at which at least one other one of the distillation tiles has generated one or more other distilled magic states of the distilled magic states.

2 . The system of claim 1 , wherein, to generate the distilled magic states, the one or more computing devices are further configured to cause the one or more quantum hardware devices to perform a temporally encoded lattice surgery based (TELS-based) magic state distillation protocol using the distillation tiles.

3 . The system of claim 2 , wherein the determination of the layout for the distillation tiles is based, at least in part, on one or more classical error-correcting codes to be used for the TELS-based magic state distillation protocol.

4 . The system of claim 1 , wherein respective distillation tiles of the magic state factory comprising distillation tiles, implemented via the rectangular patches of the topological quantum codes, comprise:

one or more rectangular patches, of the rectangular patches, configured to implement respective magic states used for the TELS-based magic state distillation protocol;

one or more additional rectangular patches, of the rectangular patches, configured to implement respective magic states used to perform, at least in part, π/8 rotations for the TELS-based magic state distillation protocol; and

one or more other rectangular patches, of the rectangular patches, configured to implement respective distilled magic state storage cells.

5 . The system of claim 1 , wherein:

respective distillation tiles of the magic state factory comprising distillation tiles, implemented via the rectangular patches of the topological quantum codes, comprise twist defects; and

to generate the distilled magic states, the one or more computing devices are further configured to further cause the one or more quantum hardware devices to perform a twist-based TELS-based magic state distillation protocol using the distillation tiles.

6 . The system of claim 1 , wherein:

the determination of the layout for the distillation tiles is such that a second boundary of the respective rectangular patch boundaries is also accessible, via the routing space or an additional routing space, by the processing core of the quantum computer; and

the second boundary is a same logical boundary as the first boundary of the respective rectangular patch boundaries.

7 . The system of claim 1 , wherein:

the quantum algorithm is represented as a parallelizable Pauli set using Pauli-based computation; and

the one or more computing devices are further configured to determine a number of distillation tiles to be implemented in the magic state factory, wherein the determination of the number of distillation tiles is based, at least in part, on a size of the parallelizable Pauli set.

8 . The system of claim 7 , wherein:

to determine the round robin scheduling, the one or more computing devices are further configured to determine an amount of time used to generate a given one or more distilled magic states using the determined layout for the distillation tiles; and

the one or more computing devices are further configured to determine the number of distillation tiles to be implemented in the magic state factory additionally based, at least in part, on a relationship between the amount of time used to generate the given one or more distilled magic states and an additional time used during the execution of the quantum algorithm.

9 . The system of claim 1 , wherein the one or more computing devices are further configured to determine the round robin scheduling based, at least in part, on a time to generate a given one or more distilled magic states using the determined layout for the distillation tiles.

10 . A method, comprising:

executing a quantum algorithm on a quantum computer that uses topological quantum codes, wherein executing the quantum algorithm comprises:

determining a round robin scheduling to be used in generating distilled magic states, using distillation tiles implemented in a magic state factory of the quantum computer, for the executing the quantum algorithm, wherein a first moment in time at which a given one of the distillation tiles has generated one or more distilled magic states of the distilled magic states is offset from a second moment in time at which at least one other one of the distillation tiles has generated one or more other distilled magic states of the distilled magic states; and

generating the distilled magic states, using the distillation tiles, for the executing the quantum algorithm, wherein the generating is based, at least in part, on the determined round robin scheduling.

11 . The method of claim 10 , wherein the generating the distilled magic states, using the distillation tiles, comprises performing a temporally encoded lattice surgery based (TELS-based) magic state distillation protocol using the distillation tiles.

12 . The method of claim 10 , wherein the determining a round robin scheduling comprises:

determining an amount of time used to generate a given one or more distilled magic states using the distillation tiles; and

determining a number of distillation tiles to be implemented in the magic state factory based, at least in part, on a relationship between the amount of time used to generate the given one or more distilled magic states and an additional time used during the execution of the quantum algorithm.

13 . The method of claim 10 , further comprising:

determining a size of a parallelizable Pauli set that represents the quantum algorithm using Pauli-based computation; and

determining a number of distillation tiles to be implemented in the magic state factory based, at least in part, on the size of the parallelizable Pauli set, and

wherein the determining the round robin scheduling to be used in the generating the distilled magic states is based, at least in part, on the determined size of the parallelizable Pauli set and on the determined number of distillation tiles to be implemented in the magic state factory.

14 . The method of claim 10 , wherein the executing the quantum algorithm on the quantum computer that uses topological quantum codes further comprises determining a layout for the distillation tiles implemented in the magic state factory of the quantum computer, wherein:

the distillation tiles are implemented via patches of the topological quantum codes; and

a first boundary of respective patch boundaries within the distillation tiles is accessible, via a routing space, by a processing core of the quantum computer.

15 . The method of claim 14 , wherein the determining the layout for the distillation tiles is based, at least in part, on a type of classical error-correcting code to be used for the executing the quantum algorithm.

16 . A non-transitory, computer-readable, medium storing program instructions that, when executed on or across one or more processors, cause the one or more processors to:

cause a quantum algorithm to be executed on a quantum computer that uses topological quantum codes, wherein to execute the quantum algorithm on the quantum computer, the program instructions further cause the one or more processors to:

determine a round robin scheduling to be used in generating distilled magic states, using distillation tiles implemented in a magic state factory of the quantum computer, for the execution of the quantum algorithm, wherein a first moment in time at which a given one of the distillation tiles has generated one or more distilled magic states of the distilled magic states is offset from a second moment in time at which at least one other one of the distillation tiles has generated one or more other distilled magic states of the distilled magic states; and

generate the distilled magic states, using the distillation tiles, for the execution of the quantum algorithm, wherein the generation is based, at least in part, on the determined layout for the distillation tiles and the determined round robin scheduling.

17 . The non-transitory, computer-readable medium of claim 16 , wherein to generate the distilled magic states, using the distillation tiles, the program instructions further cause the one or more processors to perform a temporally encoded lattice surgery based (TELS-based) magic state distillation protocol.

18 . The non-transitory, computer-readable medium of claim 16 , wherein to generate the distilled magic states, using the distillation tiles, the program instructions further cause the one or more processors to determine a layout for distillation tiles implemented in a magic state factory of the quantum computer, wherein:

the distillation tiles are implemented via patches of the topological quantum codes; and

a first boundary of respective patch boundaries within the distillation tiles is accessible, via a routing space, by a processing core of the quantum computer.

19 . The non-transitory, computer-readable medium of claim 18 , wherein:

a second boundary of the respective patch boundaries is also accessible, via the routing space or an additional routing space, by the processing core of the quantum computer, wherein the second boundary is a same logical boundary as the first boundary; and

to generate the distilled magic states, using the distillation tiles, the program instructions further cause the one or more processors to perform a parallelized TELS-based magic state distillation protocol.

20 . The non-transitory, computer-readable medium of claim 16 , wherein to generate the distilled magic states, using the distillation tiles, for the execution of the quantum algorithm, the program instructions further cause the one or more processors to:

apply the determined round robin scheduling, wherein the determined round robin scheduling is such that an amount of time to generate a given one or more distilled magic states is less than or equal to a total amount of time for the execution of the quantum algorithm.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 13, 2022
From: CHAMBERLAND, CHRISTOPHER; PRABHU, PRITHVIRAJ
To: AMAZON TECHNOLOGIES, INC.
Reel/Frame 062069/0565 →
Continuity (1)
Provisional Application 63381246 · Oct 27, 2022
References Cited (64)
US 11308252B1 · Piveteau · 2022 [cited by examiner]
US 11580436B2 · Chamberland · 2023 [cited by applicant]
US 20160191077A1 · Goto · 2016 [cited by examiner]
US 20210365315A1 · Reilly · 2021 [cited by applicant]
US 20210374588A1 · Gidney · 2021 [cited by applicant]
US 20220253742A1 · Zheng · 2022 [cited by applicant]
US 20220414509A1 · Haah · 2022 [cited by applicant]
US 20230071000A1 · Higgott · 2023 [cited by applicant]
US 20230394350A1 · Bremner · 2023 [cited by applicant]
U.S. Appl. No. 17/545,895, filed Dec. 8, 2021, Christopher Chamberland, et al. [cited by applicant]
U.S. Appl. No. 17/545,906, filed Dec. 8, 2021, Christopher Chamberland, et al. [cited by applicant]
U.S. Appl. No. 17/545,914, filed Dec. 8, 2021, Christopher Chamberland, et al. [cited by applicant]
U.S. Appl. No. 17/545,921, filed Dec. 8, 2021, Christopher Chamberland, et al. [cited by applicant]
U.S. Appl. No. 17/707,811, filed Mar. 29, 2022, Christopher Chamberland, et al. [cited by applicant]
U.S. Appl. No. 18/064,908, filed Dec. 12, 2022, Christopher Chamberland, et al. [cited by applicant]
U.S. Appl. No. 18/064,906, filed Dec. 12, 2022, Christopher Chamberland, et al. [cited by applicant]
A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” Phys. Rev. A 86, 032324 (2012 American Physical Society), pp. 1-48. [cited by applicant]
S. Bravyi and J. Haah, “Magic-state distillation with low overhead,” Phys. Rev. A 86, 052329 (2012 American Physical Society), pp. 1-10. [cited by applicant]
C. Jones, “Low-overhead constructions for the fault-tolerant Toffoli gate, ” Phys. Rev. A 87, 022328 (2013); arXIV Preprint arXiv:1212.5069v1 pp. 1-5. [cited by applicant]
T. J. Yoder, R. Takagi, and I. L. Chuang, “Universal faul-ttolerant gates on concatenated stabilizer codes,” Phys. Rev. X 6, 031039 (Published by the American Physical Society 2016), pp. 1-25. [cited by applicant]
C. Chamberland, T. Jochym-O'Connor, and R. Laflamme, “Overhead analysis of universal concatenated quantum codes,” Phys. Rev. A 95, 022313 (2017); arXiv preprint: arXiv:1609.07497v3, pp. 1-25. [cited by applicant]
C. Chamberland and T. Jochym-O'Connor, “Error suppression via complementary gauge choices in Reed-Muller codes,” Quantum Science and Technology 2, 035008 (2017), pp. 1-15. [cited by applicant]
M. E. Beverland, A. Kubica, and K. M. Svore, “Cost of universality: a comparative study of the overhead of state distillation and code switching with color codes,” PRX Quantum 2, 020341 (Published by the American Physic… [cited by applicant]
C. Chamberland and A. W. Cross, “Fault-tolerant magic state preparation with flag qubits,” Quantum vol. 3, pp. 1-26 (2019). [cited by applicant]
D. Litinski, “A game of surface codes: Large-scale quantum computing with lattice surgery,” Quantum vol. 3, 128 (2019), pp. 1-37. [cited by applicant]
D. Litinski, “Magic State Distillation: Not as Costly as You Think,” Quantum 3, 205 (2019), pp. 1-22. [cited by applicant]
C. Chamberland and K. Noh, “Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits”, npj Quantum Information 6, 91 (2020), pp. 1-12. [cited by applicant]
C. Chamberland, K. Noh, P. Arrangoiz-Arriola, E. T. Campbell, C. T. Hann, J. Iverson, H. Putterman, T. C. Bohdanowicz, S. T. Flammia, A. Keller, G. Refael, J. Preskill, L. Jiang, A. H. Safavi-Naeini, O. Painter, and F. … [cited by applicant]
C. Chamberland and E. T. Campbell, “Universal quantum computing with twist-free and temporally encoded lattice surgery,” PRX Quantum 3, 010331 (2022), pp. 1-25. [cited by applicant]
N. Shutty and C. Chamberland, “Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories,” Phys. Rev. Applied 18, 014072 (Published by the American… [cited by applicant]
S. Bravyi and A. Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas,” Phys. Rev. A 71, 022316 (The American Physical Society 2005), pp. 1-14. [cited by applicant]
A. M. Meier, B. Eastin, and E. Knill, “Magic-state distillation with the four-qubit code,” Quantum Info. Comput. 13, 195-209 (2013); arXiv preprint: arXiv:1204.4221v1, pp. 1-10. [cited by applicant]
H. Bombin and M. A. Martin-Delgado, “Topological quantum distillation,” Phys. Rev. Lett. 97, 180501 (2006); arXiv preprint: arXiv:quant-ph/0605138v3, pp. 1-4. [cited by applicant]
E. T. Campbell and M. Howard, Magic state parity-checker with pre-distilled components, Quantum 2, 56 (2018); arXiv Preprint: arXiv:1709.02214v3, pp. 1-18. [cited by applicant]
A. G. Fowler and C. Gidney, “Low overhead quantum computation using lattice surgery,” arXiv preprint arXiv:1808.06709 (2018), pp. 1-15. [cited by applicant]
D. Litinski and F. v. Oppen, “Lattice surgery with a twist: Simplifying Clifford gates of surface codes,” Quantum 2, 62 (2018); arXiv Preprint: arXiv:1709.02318v2, pp. 1-16. [cited by applicant]
C. Chamberland and E. T. Campbell, “Circuit-level protocol and analysis for twist-based lattice surgery,” Phys. Rev. Research 4, 023090 ( Published by the American Physical Society 2022), pp. 1-11. [cited by applicant]
H. Bombin, C. Dawson, R. V. Mishmash, N. Nickerson, F. Pastawski, and S. Roberts, Logical blocks for fault-tolerant topological quantum computation, arXiv preprint: arXiv:2112.12160 (2021), pp. 1-34. [cited by applicant]
C. Gidney, “Stability experiments: The overlooked dual of memory experiments,” Quantum 6, 786 (2022), arXiv Preprint arXiv:2204.13834v2, pp. 1-12. [cited by applicant]
O. Higgott, T. C. Bohdanowicz, A. Kubica, S. T. Flammia, and E. T. Campbell, “Fragile boundaries of tailored surface codes and improved decoding of circuit-level noise,” arXiv preprint , arXiv:2203.04948 (2022), pp. 1-1… [cited by applicant]
D. Deutsch, “Quantum computational networks,” Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 425, 73-90 (1989). [cited by applicant]
A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Phys. Rev. A 52, 3457 (1995); arXiv preprint arXiv:qu… [cited by applicant]
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, “A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem,” Science 292, 472 (2001), arXiv preprint arXiv:qua… [cited by applicant]
D. Gottesman and I. L. Chuang, Quantum Teleportation is a Universal Computational Primitive, Nature (London) 402, 390 (1999), arXiv preprint arXiv:quant-ph/9908010, pp. 1-6. [cited by applicant]
P. Aliferis and D. W. Leung, “Computation by measurements: a unifying picture,” Phys. Rev. A 70, 062314, ( The American Physical Society 2004), pp. 1-11. [cited by applicant]
H. J. Briegel, D. E. Browne, W. D{umlaut over ( )}ur, R. Raussendorf, and M. Van den Nest, “Measurement-based quantum computation,” Nature Physics 5, 19 (2009), arXiv preprint arXiv:0910.1116v2, pp. 1-20. [cited by applicant]
S. Bartolucci, p. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, F. Pastawski, T. Rudolph, and C. Sparrow, Fusion-based quantum computation, arXiv preprint 1… [cited by applicant]
S. Bravyi, G. Smith, and J. A. Smolin, “Trading Classical and Quantum Computational Resources,” Phys. Rev. X 6, 021043 (2016), arXiv preprint arXiv:1506.01396v1, pp. 1-14. [cited by applicant]
I. H. Kim, Y.-H. Liu, S. Pallister, W. Pol, S. Roberts, and E. Lee, “Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules,” Phys. Rev. Research 4, 023019 … [cited by applicant]
A. J. Landahl and C. Ryan-Anderson, “Quantum computing by color-code lattice surgery,” arXiv preprint (2014), arXiv:1407.5103. [cited by applicant]
C. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, “Surface code quantum computing by lattice surgery,” New Journal of Physics 14, 123011 ( IOP Publishing Ltd and Deutsche Physikalische Gesellschaft 2012), pp. 1-28. [cited by applicant]
M. G. Gowda and p. K. Sarvepalli, “Color codes with twists: Construction and universal-gate-set implementation,” Phys. Rev. A 104, 012603 (2021), arXiv preprint arXiv:2104.03669 , pp. 1-22. [cited by applicant]
D. Herr, A. Paler, S. J. Devitt, and F. Nori, “Time versus Hardware: Reducing Qubit Counts with a (Surface Code) Data Bus,” arXiv preprint (2019), arXiv:1902.08117, pp. 1-24. [cited by applicant]
J. Haah and M. B. Hastings, “Codes and protocols for distilling T, controlled-S, and Toffoli gates,” Quantum 2, 71 (2018), 1709.02832, pp. 1-29. [cited by applicant]
S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,” Phys. Rev. A 70, 052328 (2004), pp. 1-15. [cited by applicant]
C. Vuillot, L. Lao, B. Criger, C. G. Almud'ever, K. Bertels, and B. M. Terhal, “Code deformation and lattice surgery are gauge fixing,” New Journal of Physics 21, 033028 (2019), pp. 1-21. [cited by applicant]
S. Singh, A. S. Darmawan, B. J. Brown, and S. Puri, “High-fidelity magic-state preparation with a biased-noise architecture,” Phys. Rev. A 105, 052410 (2022 American Physical Society), pp. 1-9. [cited by applicant]
S. Bravyi and A. Kitaev, “Universal quantum computation with ideal Clifford gates and noisy ancillas,” Phys. Rev. A 71, 022316 (2005 The American Physical Society), pp. 1-14. [cited by applicant]
J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, “Magic state distillation with low space overhead and optimal asymptotic input count,” Quantum 1, 31 (2017), pp. 1-42. [cited by applicant]
L. Skoric, D. E. Browne, K. M. Barnes, N. I. Gillespie, and E. T. Campbell, “Parallel window decoding enables scalable fault tolerant quantum computation,” arXiv eprints , arXiv:2209.08552 (2022), pp. 1-12. [cited by applicant]
C. Chamberland, L. Goncalves, P. Sivarajah, E. Peterson, and S. Grimberg, “Techniques for combining fast local decoders with global decoders under circuit-level noise,” arXiv e-prints , arXiv:2208.01178 (2022), pp. 1-29. [cited by applicant]
S. C. Smith, B. J. Brown, and S. D. Bartlett, “A local pre-decoder to reduce the bandwidth and latency of quantum error correction,” arXiv e-prints , arXiv:2208.04660 (2022), pp. 1-16. [cited by applicant]
X. Tan, F. Zhang, R. Chao, Y. Shi, and J. Chen, “Scalable surface code decoders with parallelization in time,” arXiv e-prints , arXiv:2209.09219 (2022), pp. 1-24. [cited by applicant]
H. Bombin, C. Dawson, R. V. Mishmash, N. Nickerson, F. Pastawski, and S. Roberts, “Logical blocks for fault-tolerant topological quantum computation,” arXiv e-prints , arXiv:2112.12160 (2021), pp. 1-34. [cited by applicant]
Cited By (1)
US 12,717,559