search

QuantumSavory / QuantumClifford.jl

Clifford circuits, graph states, and other quantum Stabilizer formalism tools.
MIT License
120 stars 47 forks source link

StackOverflowError in `tensor` products involving some `AbstractStabilizer` types #339

Open Fe-r-oz opened 3 months ago

Fe-r-oz commented 3 months ago

Describe the bug 🐞

My assumption is that since we have to implement sm ⊗ S"X" where sm.stab of same type as md, therefore this md ⊗ S"X" should work?

Expected behavior

Since there is no method definition error which means that there should be no stackoverflow error hopefully.

Minimal Reproducible Example 👇

julia> md = MixedDestabilizer(T"Z//X", 1)
𝒟ℯ𝓈𝓉𝒶𝒷
+ Z
𝒮𝓉𝒶𝒷
+ X

julia> md ⊗ S"X"

Error & Stacktrace or other complete output produced by the MRE ⚠️

ERROR: StackOverflowError:
Stacktrace:
     [1] mapfoldl
       @ ./reduce.jl:175 [inlined]
     [2] #foldl#299
       @ ./reduce.jl:198 [inlined]
     [3] tensor(::MixedDestabilizer{QuantumClifford.Tableau{…}}, ::Stabilizer{QuantumClifford.Tableau{…}})
       @ QuantumClifford ~/Desktop/New/temp/QuantumClifford.jl/src/linalg.jl:165
     [4] (::Base.BottomRF{…})(acc::MixedDestabilizer{…}, x::Stabilizer{…})
       @ Base ./reduce.jl:86
     [5] afoldl(op::Base.BottomRF{…}, a::MixedDestabilizer{…}, bs::Stabilizer{…})
       @ Base ./operators.jl:544
     [6] _foldl_impl(op::Base.BottomRF{typeof(tensor)}, init::MixedDestabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Stabilizer{…}})                                                                                                                       
       @ Base ./reduce.jl:68
     [7] foldl_impl(op::Base.BottomRF{typeof(tensor)}, nt::MixedDestabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Stabilizer{…}})                                                                                                                          
       @ Base ./reduce.jl:48
     [8] mapfoldl_impl(f::typeof(identity), op::typeof(tensor), nt::MixedDestabilizer{…}, itr::Tuple{…})
       @ Base ./reduce.jl:44
     [9] mapfoldl(f::Function, op::Function, itr::Tuple{Stabilizer{…}}; init::MixedDestabilizer{QuantumClifford.Tableau{…}})
       @ Base ./reduce.jl:175
--- the last 9 lines are repeated 6664 more times ---
 [59986] mapfoldl
       @ ./reduce.jl:175 [inlined]
 [59987] #foldl#299
       @ ./reduce.jl:198 [inlined]
 [59988] tensor(::MixedDestabilizer{QuantumClifford.Tableau{…}}, ::Stabilizer{QuantumClifford.Tableau{…}})
       @ QuantumClifford ~/Desktop/New/temp/QuantumClifford.jl/src/linalg.jl:165
Some type information was truncated. Use `show(err)` to see complete types.

Environment (please complete the following information):

QuantumClifford v0.9.9
QuantumClifford v0.9.9
Julia Version 1.10.4
Commit 48d4fd48430 (2024-06-04 10:41 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
Fe-r-oz commented 2 months ago

It seems the issue is not specific to MixedDestabilizer as the title suggests, but it's related to type compatibility and infinite recursion stemming from tensor(ops::AbstractStabilizer...) in linalg.jl. TODO at line 164 provides helpful optimization suggestion about converting to common type.

https://github.com/QuantumSavory/QuantumClifford.jl/blob/e51a142d8c6b8300cfa1b417b677c7e349a1bb0b/src/linalg.jl#L164

In general, The unmarked tasks give error at the moment as seen from the MREs.

All good:

Minimal Reproducible Example 2 👇

julia> random_stabilizer(1) ⊗ random_destabilizer(2)

Error & Stacktrace or other complete output produced by the MRE 2 ⚠️

ERROR: StackOverflowError:
Stacktrace:
     [1] tensor(::Stabilizer{QuantumClifford.Tableau{…}}, ::Destabilizer{QuantumClifford.Tableau{…}})
       @ QuantumClifford ~/Desktop/New/NONSTABILIZER/tasksone/QuantumClifford.jl/src/linalg.jl:165
     [2] (::Base.BottomRF{…})(acc::Stabilizer{…}, x::Destabilizer{…})
       @ Base ./reduce.jl:86
     [3] afoldl(op::Base.BottomRF{…}, a::Stabilizer{…}, bs::Destabilizer{…})
       @ Base ./operators.jl:544
     [4] _foldl_impl(op::Base.BottomRF{…}, init::Stabilizer{…}, itr::Tuple{…})
       @ Base ./reduce.jl:68
     [5] foldl_impl(op::Base.BottomRF{typeof(tensor)}, nt::Stabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Destabilizer{…}})                                                                                                               
       @ Base ./reduce.jl:48
     [6] mapfoldl_impl(f::typeof(identity), op::typeof(tensor), nt::Stabilizer{…}, itr::Tuple{…})
       @ Base ./reduce.jl:44
     [7] mapfoldl(f::Function, op::Function, itr::Tuple{Destabilizer{…}}; init::Stabilizer{QuantumClifford.Tableau{…}})
       @ Base ./reduce.jl:175
     [8] mapfoldl
       @ ./reduce.jl:175 [inlined]
     [9] #foldl#299
       @ ./reduce.jl:198 [inlined]
--- the last 9 lines are repeated 6664 more times ---
 [59986] tensor(::Stabilizer{QuantumClifford.Tableau{…}}, ::Destabilizer{QuantumClifford.Tableau{…}})
       @ QuantumClifford ~/Desktop/New/NONSTABILIZER/tasksone/QuantumClifford.jl/src/linalg.jl:165
Some type information was truncated. Use `show(err)` to see complete types

Minimal Reproducible Example 3 👇

julia> random_destabilizer(2) ⊗ random_destabilizer(2)

Error & Stacktrace or other complete output produced by the MRE 3 ⚠️

ERROR: StackOverflowError:
Stacktrace:
     [1] afoldl(op::Base.BottomRF{…}, a::Destabilizer{…}, bs::Destabilizer{…})
       @ Base ./operators.jl:540
     [2] _foldl_impl(op::Base.BottomRF{typeof(tensor)}, init::Destabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Destabilizer{…}})
       @ Base ./reduce.jl:68
     [3] foldl_impl(op::Base.BottomRF{typeof(tensor)}, nt::Destabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Destabilizer{…}})
       @ Base ./reduce.jl:48
     [4] mapfoldl_impl(f::typeof(identity), op::typeof(tensor), nt::Destabilizer{…}, itr::Tuple{…})
       @ Base ./reduce.jl:44
     [5] mapfoldl(f::Function, op::Function, itr::Tuple{Destabilizer{…}}; init::Destabilizer{QuantumClifford.Tableau{…}})
       @ Base ./reduce.jl:175
     [6] mapfoldl
       @ ./reduce.jl:175 [inlined]
     [7] #foldl#299
       @ ./reduce.jl:198 [inlined]
     [8] tensor(::Destabilizer{QuantumClifford.Tableau{…}}, ::Destabilizer{QuantumClifford.Tableau{…}})
       @ QuantumClifford ~/Desktop/New/NONSTABILIZER/tasksone/QuantumClifford.jl/src/linalg.jl:165
     [9] (::Base.BottomRF{typeof(tensor)})(acc::Destabilizer{QuantumClifford.Tableau{…}}, x::Destabilizer{QuantumClifford.Tableau{…}})                                                                                                                        
       @ Base ./reduce.jl:86
    [10] afoldl(op::Base.BottomRF{…}, a::Destabilizer{…}, bs::Destabilizer{…})
       @ Base ./operators.jl:544
--- the last 9 lines are repeated 6664 more times ---
 [59987] _foldl_impl(op::Base.BottomRF{typeof(tensor)}, init::Destabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Destabilizer{…}})                                                                                                                          
       @ Base ./reduce.jl:68
 [59988] foldl_impl(op::Base.BottomRF{typeof(tensor)}, nt::Destabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{Destabilizer{…}})                                                                                                                             
       @ Base ./reduce.jl:48
Some type information was truncated. Use `show(err)` to see complete types.

Minimal Reproducible Example 4 👇

julia> mixeds = MixedStabilizer(S"XXX ZZ_ _ZZ");
julia> mixeds ⊗ mixeds

Error & Stacktrace or other complete output produced by the MRE 4 ⚠️

ERROR: StackOverflowError:
Stacktrace:
     [1] mapfoldl(f::Function, op::Function, itr::Tuple{MixedStabilizer{…}}; init::MixedStabilizer{QuantumClifford.Tableau{…}})
       @ Base ./reduce.jl:175
     [2] mapfoldl
       @ ./reduce.jl:175 [inlined]
     [3] #foldl#299
       @ ./reduce.jl:198 [inlined]
     [4] tensor(::MixedStabilizer{QuantumClifford.Tableau{…}}, ::MixedStabilizer{QuantumClifford.Tableau{…}})
       @ QuantumClifford ~/Desktop/New/NONSTABILIZER/tasksone/QuantumClifford.jl/src/linalg.jl:165
     [5] (::Base.BottomRF{…})(acc::MixedStabilizer{…}, x::MixedStabilizer{…})
       @ Base ./reduce.jl:86
     [6] afoldl(op::Base.BottomRF{…}, a::MixedStabilizer{…}, bs::MixedStabilizer{…})
       @ Base ./operators.jl:544
     [7] _foldl_impl(op::Base.BottomRF{…}, init::MixedStabilizer{…}, itr::Tuple{…})
       @ Base ./reduce.jl:68
     [8] foldl_impl(op::Base.BottomRF{typeof(tensor)}, nt::MixedStabilizer{QuantumClifford.Tableau{…}}, itr::Tuple{MixedStabilizer{…}})                                                                                                                       
       @ Base ./reduce.jl:48
     [9] mapfoldl_impl(f::typeof(identity), op::typeof(tensor), nt::MixedStabilizer{…}, itr::Tuple{…})
       @ Base ./reduce.jl:44
--- the last 9 lines are repeated 6664 more times ---
 [59986] mapfoldl(f::Function, op::Function, itr::Tuple{MixedStabilizer{…}}; init::MixedStabilizer{QuantumClifford.Tableau{…}})
       @ Base ./reduce.jl:175
 [59987] mapfoldl
       @ ./reduce.jl:175 [inlined]
Some type information was truncated. Use `show(err)` to see complete types.

Compared to MRE4, these all good:

julia> ghz(3) ⊗ ghz(3)
+ XXX___
+ ZZ____
+ _ZZ___
+ ___XXX
+ ___ZZ_
+ ____ZZ

julia> random_stabilizer(1) ⊗ random_stabilizer(1)
- Y_
+ _Z

julia> random_stabilizer(2) ⊗ random_stabilizer(2)
- ZZ__
- XX__
- __Y_
- ___X