QCHackers
A polynomial-time algorithm for finding correlation surfaces
A new algorithm for finding correlation surfaces, exponentially faster than the original algorithm, doesn't require gflow, and doesn't need info about input and output leaf nodes. See also #696.
It's currently in src/tqec/interop/pyzx/correlation_experimental.py as it's still in a draft form. I plan to add mid-exploration pruning based on leaf nodes, change the data structure to be X-and-Z-based, and polish it more.
Happy to discuss how it should be modified to best integrate into the existing codebase. For example, the reduce_to_minimal_generators argument doesn't make sense anymore since the algorithm doesn't return all possible correlation surfaces. And how the tests should be adapted accordingly (it should pass all tests up to equivalence, except for those requiring all possible correlation surfaces).
Basic benchmarking using stacked Steane encoding block graphs:
Finding 7 correlation surfaces for block graph with 19 cubes, 20 pipes, and 7 leaf cubes took 0.01 s
Finding 8 correlation surfaces for block graph with 35 cubes, 40 pipes, and 8 leaf cubes took 0.03 s
Finding 9 correlation surfaces for block graph with 51 cubes, 60 pipes, and 9 leaf cubes took 0.07 s
Finding 10 correlation surfaces for block graph with 67 cubes, 80 pipes, and 10 leaf cubes took 0.13 s
Finding 11 correlation surfaces for block graph with 83 cubes, 100 pipes, and 11 leaf cubes took 0.29 s
Finding 12 correlation surfaces for block graph with 99 cubes, 120 pipes, and 12 leaf cubes took 0.31 s
Finding 13 correlation surfaces for block graph with 115 cubes, 140 pipes, and 13 leaf cubes took 0.81 s
Finding 14 correlation surfaces for block graph with 131 cubes, 160 pipes, and 14 leaf cubes took 0.84 s
Finding 15 correlation surfaces for block graph with 147 cubes, 180 pipes, and 15 leaf cubes took 1.63 s
Finding 16 correlation surfaces for block graph with 163 cubes, 200 pipes, and 16 leaf cubes took 1.62 s
Finding 17 correlation surfaces for block graph with 179 cubes, 220 pipes, and 17 leaf cubes took 2.22 s
Finding 18 correlation surfaces for block graph with 195 cubes, 240 pipes, and 18 leaf cubes took 2.85 s
Finding 19 correlation surfaces for block graph with 211 cubes, 260 pipes, and 19 leaf cubes took 4.63 s
Finding 20 correlation surfaces for block graph with 227 cubes, 280 pipes, and 20 leaf cubes took 5.85 s
Finding 21 correlation surfaces for block graph with 243 cubes, 300 pipes, and 21 leaf cubes took 7.03 s
Finding 22 correlation surfaces for block graph with 259 cubes, 320 pipes, and 22 leaf cubes took 7.10 s
Finding 23 correlation surfaces for block graph with 275 cubes, 340 pipes, and 23 leaf cubes took 10.39 s
Finding 24 correlation surfaces for block graph with 291 cubes, 360 pipes, and 24 leaf cubes took 12.19 s
Finding 25 correlation surfaces for block graph with 307 cubes, 380 pipes, and 25 leaf cubes took 14.27 s
Finding 26 correlation surfaces for block graph with 323 cubes, 400 pipes, and 26 leaf cubes took 16.79 s
Finding 27 correlation surfaces for block graph with 339 cubes, 420 pipes, and 27 leaf cubes took 19.30 s
Finding 28 correlation surfaces for block graph with 355 cubes, 440 pipes, and 28 leaf cubes took 18.09 s
Finding 29 correlation surfaces for block graph with 371 cubes, 460 pipes, and 29 leaf cubes took 20.49 s
Finding 30 correlation surfaces for block graph with 387 cubes, 480 pipes, and 30 leaf cubes took 25.62 s
Excellent, would you be willing and able to talk about your new algorithm at an upcoming group meeting? Perhaps in two weeks?
Best, Austin.
On Fri, Sep 26, 2025 at 9:58 AM Tianyi Hao @.***> wrote:
A new algorithm for finding correlation surfaces, exponentially faster than the original algorithm, doesn't require gflow, and doesn't need info about input and output leaf nodes. See also #696 https://github.com/tqec/tqec/issues/696.
It's currently in src/tqec/interop/pyzx/correlation_experimental.py as it's still in a draft form. I plan to add mid-exploration pruning based on leaf nodes, change the data structure to be X-and-Z-based, and polish it more.
Happy to discuss how it should be modified to best integrate into the existing codebase. For example, the reduce_to_minimal_generators argument doesn't make sense anymore since the algorithm doesn't return all possible correlation surfaces. And how the tests should be adapted accordingly (it should pass all tests up to equivalence, except for those requiring all possible correlation surfaces).
Basic benchmarking using stacked Steane encoding block graphs:
Finding 7 correlation surfaces for block graph with 19 cubes, 20 pipes, and 7 leaf cubes took 0.01 s Finding 8 correlation surfaces for block graph with 35 cubes, 40 pipes, and 8 leaf cubes took 0.03 s Finding 9 correlation surfaces for block graph with 51 cubes, 60 pipes, and 9 leaf cubes took 0.07 s Finding 10 correlation surfaces for block graph with 67 cubes, 80 pipes, and 10 leaf cubes took 0.13 s Finding 11 correlation surfaces for block graph with 83 cubes, 100 pipes, and 11 leaf cubes took 0.29 s Finding 12 correlation surfaces for block graph with 99 cubes, 120 pipes, and 12 leaf cubes took 0.31 s Finding 13 correlation surfaces for block graph with 115 cubes, 140 pipes, and 13 leaf cubes took 0.81 s Finding 14 correlation surfaces for block graph with 131 cubes, 160 pipes, and 14 leaf cubes took 0.84 s Finding 15 correlation surfaces for block graph with 147 cubes, 180 pipes, and 15 leaf cubes took 1.63 s Finding 16 correlation surfaces for block graph with 163 cubes, 200 pipes, and 16 leaf cubes took 1.62 s Finding 17 correlation surfaces for block graph with 179 cubes, 220 pipes, and 17 leaf cubes took 2.22 s Finding 18 correlation surfaces for block graph with 195 cubes, 240 pipes, and 18 leaf cubes took 2.85 s Finding 19 correlation surfaces for block graph with 211 cubes, 260 pipes, and 19 leaf cubes took 4.63 s Finding 20 correlation surfaces for block graph with 227 cubes, 280 pipes, and 20 leaf cubes took 5.85 s Finding 21 correlation surfaces for block graph with 243 cubes, 300 pipes, and 21 leaf cubes took 7.03 s Finding 22 correlation surfaces for block graph with 259 cubes, 320 pipes, and 22 leaf cubes took 7.10 s Finding 23 correlation surfaces for block graph with 275 cubes, 340 pipes, and 23 leaf cubes took 10.39 s Finding 24 correlation surfaces for block graph with 291 cubes, 360 pipes, and 24 leaf cubes took 12.19 s Finding 25 correlation surfaces for block graph with 307 cubes, 380 pipes, and 25 leaf cubes took 14.27 s Finding 26 correlation surfaces for block graph with 323 cubes, 400 pipes, and 26 leaf cubes took 16.79 s Finding 27 correlation surfaces for block graph with 339 cubes, 420 pipes, and 27 leaf cubes took 19.30 s Finding 28 correlation surfaces for block graph with 355 cubes, 440 pipes, and 28 leaf cubes took 18.09 s Finding 29 correlation surfaces for block graph with 371 cubes, 460 pipes, and 29 leaf cubes took 20.49 s Finding 30 correlation surfaces for block graph with 387 cubes, 480 pipes, and 30 leaf cubes took 25.62 s
You can view, comment on, or merge this pull request online at:
https://github.com/tqec/tqec/pull/707 Commit Summary
- 49da073 https://github.com/tqec/tqec/pull/707/commits/49da073d897359dd18633ee8c0ba4988637f6a9b draft implementation of an efficient algorithm for finding correlation surfaces
- 5cb76cc https://github.com/tqec/tqec/pull/707/commits/5cb76cc40bc85211c6fd3d48a6b082101e3a22b2 fix an over-pruning issue (concept validation)
- 309af84 https://github.com/tqec/tqec/pull/707/commits/309af8446dd1c3ebe573199d9d59031b03853966 use dict of dicts instead of networkx to represent Pauli graphs
- 2cba989 https://github.com/tqec/tqec/pull/707/commits/2cba989c4d427bcd2becf14d959d13e7e6fccb0e over-pruning issue fix attempt
- 1e5baf5 https://github.com/tqec/tqec/pull/707/commits/1e5baf549ab9e8619785dbd6d1628d9290b2a349 over-pruning issue fixed
- 5e9d8e6 https://github.com/tqec/tqec/pull/707/commits/5e9d8e6971560e7e4c6989166e05c5e6064c2762 software engineering improvements to the new correlation surface finding algorithm
File Changes
(2 files https://github.com/tqec/tqec/pull/707/files)
- A src/tqec/interop/pyzx/correlation_experimental.py https://github.com/tqec/tqec/pull/707/files#diff-97f377a7809b8ad79170d0b240756054f220ba309cc6983cbdd857307dec5293 (509)
- M src/tqec/utils/enums.py https://github.com/tqec/tqec/pull/707/files#diff-7df84898896be6593b93231171e38fc1bba103cc60f893375a8fc4043c9a0f90 (45)
Patch Links:
- https://github.com/tqec/tqec/pull/707.patch
- https://github.com/tqec/tqec/pull/707.diff
— Reply to this email directly, view it on GitHub https://github.com/tqec/tqec/pull/707, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTHWPMM2R45KLBZ3ECL3UVWB5AVCNFSM6AAAAACHTNGEXKVHI2DSMVQWIX3LMV43ASLTON2WKOZTGQ2TQMZYGYZTANY . You are receiving this because you are subscribed to this thread.Message ID: @.***>
Excellent, would you be willing and able to talk about your new algorithm at an upcoming group meeting? Perhaps in two weeks?
Of course, glad to!
@Zhaoyilunnn The "wrong" correlation surfaces in the failed tests may just be products of what the tests want, which should be totally valid (e.g., the three cnots example seems valid to me; I don't see why a correlation surface can't have both X and Z bases), but I will take a closer look tomorrow. I've seen the "non-deterministic observables" Stim error with the original algorithm before, so potentially there could be a more foundamental cause.
@Zhaoyilunnn The "wrong" correlation surfaces in the failed tests may just be products of what the tests want, which should be totally valid (e.g., the three cnots example seems valid to me; I don't see why a correlation surface can't have both X and Z bases), but I will take a closer look tomorrow. I've seen the "non-deterministic observables" Stim error with the original algorithm before, so potentially there could be a more foundamental cause.
ok I got it. So your algorithm does not produce surfaces with minimal area. I agree the above correlation surface itself is correct. However, in the original implementation, it will not generate a surface that has both X and Z basis. Because starting from each leaf node, it will propogate either a X operator or a Z operator, and a three-cnot block graph will not generate a surface like yours. Thus I guess this kind of correlation surface leads to the failure of tests.
I am not sure if the current observable annotation algorithm made any assumption on this. Maybe @inmzhang could comment on this.
I am not sure if the current observable annotation algorithm made any assumption on this. Maybe @inmzhang could comment on this.
A correlation surface that is a product of a Z-basis and X-basis correlation surface is valid but may lead to Y basis observable terminating at the ports, which requires Y-basis measurement/initialization to support the observable. The current observable annotation implementation does not take the Y-basis observable into account yet.
Nice work! I don't have much time these days and will try to review and understand the code in the next week.
So your algorithm does not produce surfaces with minimal area.
Ah, yes, I should've noted this in my original post. Because it doesn't generate all the possible correlation surfaces, we need to solve a combinatorial optimization problem if we want to minimize the area. However, I don't think minimizing the area has a huge benefit. Please correct me if my understanding is limited.
However, in the original implementation, it will not generate a surface that has both X and Z basis. Because starting from each leaf node, it will propogate either a X operator or a Z operator, and a three-cnot block graph will not generate a surface like yours. Thus I guess this kind of correlation surface leads to the failure of tests.
A correlation surface that is a product of a Z-basis and X-basis correlation surface is valid but may lead to Y basis observable terminating at the ports, which requires Y-basis measurement/initialization to support the observable. The current observable annotation implementation does not take the Y-basis observable into account yet.
Thank you for the clarifications! After the algorithm returns a generator set, we can potentially find another generator set that doesn't have Y-basis observables at the ports. But it may be easier and desirable to implement the Y-basis observable annotation.
But it may be easier and desirable to implement the Y-basis observable annotation.
Having Y-basis observable at ports means that we need to use Y-basis initialization/measurement block there to terminate the observable, which not only changes observable annotation but the circuit as well. It should always be helpful to not mix the X/Z basis when possible.
Having Y-basis observable at ports means that we need to use Y-basis initialization/measurement block there to terminate the observable, which not only changes observable annotation but the circuit as well. It should always be helpful to not mix the X/Z basis when possible.
I have some confusion. There are two cases when a port may get a Y from a correlation surface:
- The port is filled by YHalfCube, indicating a Y-basis initialization or measurement. Correlation surfaces containing Ys are perhaps unavoidable. How was this handled previously? Is it TBD with #548?
- The port is open. In this case, don't the X/Z-basis correlation surfaces also "change the circuit", as in filling the port, or am I interpreting this wrong?
The port is filled by YHalfCube, indicating a Y-basis initialization or measurement. Correlation surfaces containing Ys are perhaps unavoidable. How was this handled previously?
We do not support simulate a block graph with YHalfCubes yet, it's only possible after #548 is fixed. Yes, the Y-basis correlation basis is unavoidable and expected then, we'll handle it during building the circuit for YHalfCube.
The port is open. In this case, don't the X/Z-basis correlation surfaces also "change the circuit", as in filling the port, or am I interpreting this wrong?
Block graph with open ports can not be used for simulation or building a circuit. The concern is always at that we are required to fill a YHalfCube to terminate a Y-basis correlation surface which is more expensive than transversal X/Z basis initialization/measurement.
If your algorithm can find a generating set of correlation surface, I believe we can always reproduce a set of CSS-style correlation surface that does not mix the X/Z bases when the structure of block graph allows that.
We do not support simulate a block graph with
YHalfCubes yet, it's only possible after #548 is fixed. Yes, the Y-basis correlation basis is unavoidable and expected then, we'll handle it during building the circuit forYHalfCube.
Block graph with open ports can not be used for simulation or building a circuit. The concern is always at that we are required to fill a YHalfCube to terminate a Y-basis correlation surface which is more expensive than transversal X/Z basis initialization/measurement.
I see.
If your algorithm can find a generating set of correlation surface, I believe we can always reproduce a set of CSS-style correlation surface that does not mix the X/Z bases when the structure of block graph allows that.
Although I haven't implemented it, I do have a simple solution in my mind, which can reuse part of the code in the algorithm. Will update soon.
@afowler Hi Austin, I'm ready to present the algorithm. Would next Wednesday be a good time?
Yes, that would work well. Would you like the whole meeting?
On Thu, Oct 9, 2025, 7:03 PM Tianyi Hao @.***> wrote:
HaoTy left a comment (tqec/tqec#707) https://github.com/tqec/tqec/pull/707#issuecomment-3388028962
@afowler https://github.com/afowler Hi Austin, I'm ready to present the algorithm. Would next Wednesday be a good time?
— Reply to this email directly, view it on GitHub https://github.com/tqec/tqec/pull/707#issuecomment-3388028962, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTEPRTMGQHF6FE3XHKT3W4HYLAVCNFSM6AAAAACHTNGEXKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTGOBYGAZDQOJWGI . You are receiving this because you were mentioned.Message ID: @.***>
Would you like the whole meeting?
The presentation itself should be ~20 minutes, but could use more time for Q&A and discussing how it can be best integrated to align with the rest of tqec.
Do you have a couple of slides on your algorithm that we could feature at Munich? Please see this deck https://docs.google.com/presentation/d/1RcMXB3kWtWWyM_LOQLkxo19Zaq4atLaV1fCsWqd78PQ/edit?usp=sharing in preparation. Discussing finding correlation surfaces would be next. Do you have a deck for Wednesday?
Best, Austin.
On Thu, Oct 9, 2025 at 7:25 PM Tianyi Hao @.***> wrote:
HaoTy left a comment (tqec/tqec#707) https://github.com/tqec/tqec/pull/707#issuecomment-3388060847
Would you like the whole meeting?
The presentation itself should be ~20 minutes, but could use more time for Q&A and discussing how it can be best integrated to align with the rest of tqec.
— Reply to this email directly, view it on GitHub https://github.com/tqec/tqec/pull/707#issuecomment-3388060847, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTGBLRCQFIBGKPZQ3S33W4KJXAVCNFSM6AAAAACHTNGEXKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTGOBYGA3DAOBUG4 . You are receiving this because you were mentioned.Message ID: @.***>
Do you have a couple of slides on your algorithm that we could feature at Munich?
Yes! Please see https://1drv.ms/p/c/6cb205327248e7b5/EeHjUTUmXUFBqu9RmlAuPcQBxKYEghPdpFXGoLfB6q1xAw?e=hXLfm2. For the last slide, I plan to add benchmarking on ZX diagrams generated from Clifford+T circuits if I can get it done by Wednesday, or the above rudimentary stacked Steane encoding example otherwise.
Thanks for the slides, look forward to seeing the benchmarking data. Honestly, that would be the best thing to include in this short talk. Brief description of the algorithm, and benchmarking data. I need to submit the slides to Munich on Wednesday, but I'm sure there can be some flexibility if you still don't have the data on Wednesday.
Best, Austin.
On Sat, Oct 11, 2025 at 11:33 AM Tianyi Hao @.***> wrote:
HaoTy left a comment (tqec/tqec#707) https://github.com/tqec/tqec/pull/707#issuecomment-3393574599
Do you have a couple of slides on your algorithm that we could feature at Munich?
Yes! Please see https://1drv.ms/p/c/6cb205327248e7b5/EeHjUTUmXUFBqu9RmlAuPcQBxKYEghPdpFXGoLfB6q1xAw?e=hXLfm2 . For the last slide, I plan to add benchmarking on ZX diagrams generated from Clifford+T circuits if I can get it done by Wednesday, or the above rudimentary stacked Steane encoding example otherwise.
— Reply to this email directly, view it on GitHub https://github.com/tqec/tqec/pull/707#issuecomment-3393574599, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTD4DWAEIJR5D6NRILL3XFEQHAVCNFSM6AAAAACHTNGEXKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTGOJTGU3TINJZHE . You are receiving this because you were mentioned.Message ID: @.***>
@afowler Preliminary results updated in my slides. Some of the previous slides were also slightly modified
Through a series of algorithmic and engineering efforts, the performance of the algorithm has been drastically improved (notice the significantly expanded x-axis):
The scaling in practice is more like quadratic, due to the bottleneck being the multiplication of multiple correlation surfaces, which, in the current implementation, would need to read and perform XORs on all values in several dicts of dicts. This may not be a bottleneck when we implement it in, for example, rust, so I don't intend to attempt more involved improvements at this moment.
The problem of avoiding Y cubes is trickier than I thought. The solution I had in mind, constructing and solving a linear system, doesn't seem applicable now. I will see what else can be utilized to solve this problem.
Hey, just wanted to throw another suggestion into this: In https://github.com/maximilianruesch/fault-gadgets/blob/develop/src/faultgadget/web/compute.py (and accompanying files) I implemented a Gaussian solver for Pauli webs based on the definitions from https://arxiv.org/abs/2410.17240, and in particular based on the algorithm from https://www.cs.ox.ac.uk/people/aleks.kissinger/papers/borghans-thesis.pdf. The context in which it is implemented is a more theoretical approach in https://arxiv.org/abs/2510.08477.
This implementation should currently be roughly qubic (I have not tested it integrated with tqec since I do not have anything set up), although during development I had a similar idea to this PR: Find cuts in the graph such that combination of the different stabiliser basis of the subgraphs will be cheap, then compute the web basis of the subgraphs using the Gaussian solver (or further divide / conquer). This would also allow the computation to become parallelised (unsure if this PR does this already), and could allow finding Pauli webs on machines with limited RAM (as the linear systems you would need to store are limited in size by the maximum of the subgraph size and the most edges cut in one cut). I am currently working on implementing this, although its not quite ready yet.
Although I do not fully understand the problem with Y-cubes, perhaps it might be easier to place linear constraints on the system to be solved with the above approach?
If we're talking 3D placement of Y half cubes, a time duration must be chosen and the short dimension of these must be parallel to this time direction.
If we are talking finding correlation surfaces in a ZX graph, then only Y correlation surfaces can terminate on a Y node, or alternatively if an X correlation surface goes in, a Z correlation surface must come out, and vice versa.
On Wed, Oct 29, 2025 at 4:37 AM Maximilian Rüsch @.***> wrote:
maximilianruesch left a comment (tqec/tqec#707) https://github.com/tqec/tqec/pull/707#issuecomment-3461069577
Hey, just wanted to throw another suggestion into this: In https://github.com/maximilianruesch/fault-gadgets/blob/develop/src/faultgadget/web/compute.py (and accompanying files) I implemented a Gaussian solver for Pauli webs based on the definitions from https://arxiv.org/abs/2410.17240, and in particular based on the algorithm from https://www.cs.ox.ac.uk/people/aleks.kissinger/papers/borghans-thesis.pdf. The context in which it is implemented is a more theoretical approach in https://arxiv.org/abs/2510.08477.
This implementation should currently be roughly qubic (I have not tested it integrated with tqec since I do not have anything set up), although during development I had a similar idea to this PR: Find cuts in the graph such that combination of the different stabiliser basis of the subgraphs will be cheap, then compute the web basis of the subgraphs using the Gaussian solver (or further divide / conquer). This would also allow the computation to become parallelised (unsure if this PR does this already), and could allow finding Pauli webs on machines with limited RAM (as the linear systems you would need to store are limited in size by the maximum of the subgraph size and the most edges cut in one cut).
Although I do not fully understand the problem with Y-cubes, perhaps it might be easier to place linear constraints on the system to be solved with the above approach?
— Reply to this email directly, view it on GitHub https://github.com/tqec/tqec/pull/707#issuecomment-3461069577, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTGA5VMAHPRM2SJUCY332CRGRAVCNFSM6AAAAACHTNGEXKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTINRRGA3DSNJXG4 . You are receiving this because you were mentioned.Message ID: @.***>
@HaoTy is the problem that Y-cubes (and thus Y correlation surfaces terminating at an open node) should generally be avoided because they require some choice of time? Or is it something else?
Hey, just wanted to throw another suggestion into this: In https://github.com/maximilianruesch/fault-gadgets/blob/develop/src/faultgadget/web/compute.py (and accompanying files) I implemented a Gaussian solver for Pauli webs based on the definitions from https://arxiv.org/abs/2410.17240, and in particular based on the algorithm from https://www.cs.ox.ac.uk/people/aleks.kissinger/papers/borghans-thesis.pdf. The context in which it is implemented is a more theoretical approach in https://arxiv.org/abs/2510.08477.
This implementation should currently be roughly qubic (I have not tested it integrated with tqec since I do not have anything set up), although during development I had a similar idea to this PR: Find cuts in the graph such that combination of the different stabiliser basis of the subgraphs will be cheap, then compute the web basis of the subgraphs using the Gaussian solver (or further divide / conquer). This would also allow the computation to become parallelised (unsure if this PR does this already), and could allow finding Pauli webs on machines with limited RAM (as the linear systems you would need to store are limited in size by the maximum of the subgraph size and the most edges cut in one cut). I am currently working on implementing this, although its not quite ready yet.
Although I do not fully understand the problem with Y-cubes, perhaps it might be easier to place linear constraints on the system to be solved with the above approach?
Thank you for the information! I had a similar idea of constructing and solving a giant linear system covering all nodes, but thought it would be less favorable compared to a native graph algorithm. Although it would be naturally suitable for accelerated computing, it requires solving an O(n) by O(n) system (larger if m is not bounded by n), which, as you said, takes about O(n^3), where n is the number of vertices. When the graph is sparse, such as the bounded-degree graphs we have, the matrix is also sparse (because the rules are local), and the speed and memory footprint can likely be improved by sparse numerical methods. Still, I think a graph algorithm is a more natural solution to this problem. Eventually, with the help of time ordering from the circuit, we'd want a linear algorithm, essentially a stabilizer propagation in the circuit (but the graph doesn't necessarily have a good correspondance with the circuit after optimization/converting to lattice surgery). The algorithm in this PR (along with some changes not yet pushed) is quite close to this goal. Nothing is parallelized at this moment, but surely it can be achieved.
The Y cube problem has multiple complications. It is not very easily solvable by Gaussian elimination, if possible at all. We want to minimize the use of Y cubes, because they need an additional d/2-depth physical circuit to implement compared to X/Z initialization/measurements. But in some cases, Y cubes are needed in some of the ports for the correlation surfaces to be valid. Additionally, they can only be in the temporal direction (see #719). I think we should impose some constraints on the port-filling of the input to properly handle Y cubes.
Interesting point about Y termination of outputs. I personally think it is ok to flag a structure as not possible to simulate if the only valid correlation surfaces involve one or more Y terminations on a port that is not time aligned.
On Wed, Oct 29, 2025, 2:09 PM Tianyi Hao @.***> wrote:
HaoTy left a comment (tqec/tqec#707) https://github.com/tqec/tqec/pull/707#issuecomment-3464050725
Hey, just wanted to throw another suggestion into this: In https://github.com/maximilianruesch/fault-gadgets/blob/develop/src/faultgadget/web/compute.py (and accompanying files) I implemented a Gaussian solver for Pauli webs based on the definitions from https://arxiv.org/abs/2410.17240, and in particular based on the algorithm from https://www.cs.ox.ac.uk/people/aleks.kissinger/papers/borghans-thesis.pdf. The context in which it is implemented is a more theoretical approach in https://arxiv.org/abs/2510.08477.
This implementation should currently be roughly qubic (I have not tested it integrated with tqec since I do not have anything set up), although during development I had a similar idea to this PR: Find cuts in the graph such that combination of the different stabiliser basis of the subgraphs will be cheap, then compute the web basis of the subgraphs using the Gaussian solver (or further divide / conquer). This would also allow the computation to become parallelised (unsure if this PR does this already), and could allow finding Pauli webs on machines with limited RAM (as the linear systems you would need to store are limited in size by the maximum of the subgraph size and the most edges cut in one cut). I am currently working on implementing this, although its not quite ready yet.
Although I do not fully understand the problem with Y-cubes, perhaps it might be easier to place linear constraints on the system to be solved with the above approach?
Thank you for the information! I had a similar idea of constructing and solving a giant linear system covering all nodes, but thought it would be less favorable compared to a native graph algorithm. Although it would be naturally suitable for accelerated computing, it requires solving an O(n) by O(n) system (which, as you said, takes about O(n^3)), where n is the number of vertices. When the graph is sparse, such as the bounded-degree graphs we have, the matrix is also sparse (because the rules are local), and the speed and memory footprint can likely be improved by sparse numerical methods. Still, I think a graph algorithm is a more natural solution to this problem. Eventually, with the help of time ordering from the circuit, we'd want a linear algorithm, essentially a stabilizer propagation in the circuit (but the graph doesn't necessarily have a good correspondance with the circuit after optimization/converting to lattice surgery). The algorithm in this PR (along with some changes not yet pushed) is quite close to this goal.
The Y cube problem has multiple complications. It is not very easily solvable by Gaussian elimination, if possible at all. We want to minimize the use of Y cubes, because they need an additional d/2-depth physical circuit to implement compared to X/Z initialization/measurements. But in some cases, Y cubes are needed in some of the ports for the correlation surfaces to be valid. Additionally, they can only be in the temporal direction (see #719 https://github.com/tqec/tqec/pull/719). I think we should impose some constraints on the port-filling of the input to properly handle Y cubes.
— Reply to this email directly, view it on GitHub https://github.com/tqec/tqec/pull/707#issuecomment-3464050725, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTEWJ7FLMBDA4JA2V6T32EUKHAVCNFSM6AAAAACHTNGEXKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTINRUGA2TANZSGU . You are receiving this because you were mentioned.Message ID: @.***>