search

microsoft / Quantum

Microsoft Quantum Development Kit Samples
https://docs.microsoft.com/quantum
MIT License
3.86k stars 918 forks source link

Error in Shor's algorithm #812

Closed mahno2023 closed 1 year ago

mahno2023 commented 1 year ago

Describe the bug When trying samples/algorithms/integer-factorization on 11633=107*109, got repeating exception:

Unhandled exception. Microsoft.Quantum.Simulation.Core.ExecutionFailException: Qubit in invalid state. Expecting: Zero Expected: 0 Actual: 2.7085528264692016E-10 ---> Microsoft.Quantum.Diagnostics.AssertMeasurement on D:\a\1\s\submodules\qsharp-runtime\src\Simulation\QSharpFoundation\Diagnostics\Assert.qs:line 0 at Microsoft.Quantum.Diagnostics.AssertQubit on D:\a\1\s\submodules\qsharp-runtime\src\Simulation\QSharpFoundation\Diagnostics\AssertQubit.qs:line 0 at Microsoft.Quantum.Diagnostics.AssertAllZero on D:\a\1\s\submodules\qsharp-runtime\src\Simulation\QSharpFoundation\Diagnostics\AssertAllZero.qs:line 0 at Microsoft.Quantum.Canon.ApplyAnd on D:\a\1\s\submodules\QuantumLibraries\Standard\src\Canon\And.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.CompareGreaterThanOrEqualConstant on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Compare.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.ModularAddConstant on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Modular.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.ModularAddConstant on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Modular.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.ModularMultiplyByConstant on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Modular.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.ApplyOrderFindingOracle on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Shor.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.EstimateFrequency on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Shor.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.EstimatePeriod on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Shor.qs:line 0 at Microsoft.Quantum.Samples.IntegerFactorization.FactorSemiprimeInteger on D:\КВИ\Quantum-main\samples\algorithms\integer-factorization\Shor.qs:line 0

This run of Shor's algorithm failed: Qubit in invalid state. Expecting: Zero Expected: 0 Actual: 2.7085528264692016E-10

The "Actual" number slightly varies in different instances of this output.

To Reproduce In line 21 of samples/algorithms/integer-factorization/Program.cs change "Default = 15" to "Default = 11633", set IntegerFactorization as startup project, build and run.

Expected behavior Output:

Factors are 107 and 109

after reasonable time.

System information

Additional context Perhaps, an unneeded assertion in the core of QDK should be removed.

mahno2023 commented 1 year ago

Sorry, just typo