In[]:=
convertToProportionalStates[stateVector_List]:=Module[{probabilities,output},probabilities=Table[If[#[[i]]>0,#[[i]]^2ReplacePart[ConstantArray[0,Length[#]],{i}1],##&[]],{i,1,Length[#]}]&@stateVector;output=Catenate[Table[Table[#[[1,2]],{j,1,#[[i,1]]/Min[probabilities[[All,1]]]}],{i,1,Length[#]}]]&@probabilities;output]MultiwayShorAlgorithm[<|"Number"number_Integer,"InitialGuess"initialGuess_Integer,"CountingQubits"countingQubits_Integer,"AncillaQubits"ancillaQubits_Integer|>,stepCount_Integer,rest___]:=Module[{initialStates,basisMap,operatorAction,inputToOutput,replacements,matrixForm,conditionalModularExponential,moddedStates,quantumFourierTransform,inverseQuantumFourierTransform,finalStates},initialStates=QuantumTensorProduct[Catenate[{Table[QuantumDiscreteState["Plus"],{i,1,countingQubits}],Table[QuantumDiscreteState[{0,1},2],{j,1,ancillaQubits-1}],{QuantumDiscreteState[{1,0},2]}}]];basisMap=AssociationThread[Flatten[Table[Ket[i,j],{i,0,2^countingQubits-1},{j,0,2^ancillaQubits-1}]]Range[2^(ancillaQubits+countingQubits)]];operatorAction=Association[Table[Ket[i,0]Ket[i,Mod[initialGuess^i,number]],{i,0,2^countingQubits-1}]];inputToOutput=KeyMap[Replace[basisMap]]@(operatorAction/.basisMap);replacements=Flatten[KeyValueMap[{{#1,#2}1,{#2,#1}1,{#1,#1}0,{#2,#2}0}&,inputToOutput]];matrixForm=ReplacePart[IdentityMatrix[2^(countingQubits+ancillaQubits)],replacements];conditionalModularExponential=QuantumDiscreteOperator[N[matrixForm],Range[countingQubits+ancillaQubits]];moddedStates=conditionalModularExponential[initialStates];quantumFourierTransform=QuantumDiscreteOperator[{"Fourier",1,2^countingQubits},Range[countingQubits]];inverseQuantumFourierTransform=QuantumDiscreteOperator[Inverse[N[quantumFourierTransform["MatrixRepresentation"]]],Range[countingQubits]];finalStates=inverseQuantumFourierTransform[moddedStates];{ResourceFunction["QuantumToMultiwaySystem"][Floor[conditionalModularExponential["MatrixRepresentation"]],convertToProportionalStates[initialStates["StateVector"]],stepCount,rest],ResourceFunction["QuantumToMultiwaySystem"][Transpose[PadRight[#,Length[First[initialStates]]]&/@Transpose[PadRight[#,Length[First[initialStates]]]&/@Floor[inverseQuantumFourierTransform["MatrixRepresentation"]]]],convertToProportionalStates[moddedStates["StateVector"]],stepCount,rest]}]CompletedMultiwayShorAlgorithm[<|"Number"number_Integer,"InitialGuess"initialGuess_Integer,"CountingQubits"countingQubits_Integer,"AncillaQubits"ancillaQubits_Integer|>,stepCount_Integer,rest___]:=Module[{initialStates,basisMap,operatorAction,inputToOutput,replacements,matrixForm,conditionalModularExponential,moddedStates,quantumFourierTransform,inverseQuantumFourierTransform,finalStates,conditionalModularExponentialRules,inverseQuantumFourierTransformRules,conditionalModularExponentialCompletionRules,inverseQuantumFourierTransformCompletionRules},initialStates=QuantumTensorProduct[Catenate[{Table[QuantumDiscreteState["Plus"],{i,1,countingQubits}],Table[QuantumDiscreteState[{0,1},2],{j,1,ancillaQubits-1}],{QuantumDiscreteState[{1,0},2]}}]];basisMap=AssociationThread[Flatten[Table[Ket[i,j],{i,0,2^countingQubits-1},{j,0,2^ancillaQubits-1}]]Range[2^(ancillaQubits+countingQubits)]];operatorAction=Association[Table[Ket[i,0]Ket[i,Mod[initialGuess^i,number]],{i,0,2^countingQubits-1}]];inputToOutput=KeyMap[Replace[basisMap]]@(operatorAction/.basisMap);replacements=Flatten[KeyValueMap[{{#1,#2}1,{#2,#1}1,{#1,#1}0,{#2,#2}0}&,inputToOutput]];matrixForm=ReplacePart[IdentityMatrix[2^(countingQubits+ancillaQubits)],replacements];conditionalModularExponential=QuantumDiscreteOperator[N[matrixForm],Range[countingQubits+ancillaQubits]];moddedStates=conditionalModularExponential[initialStates];quantumFourierTransform=QuantumDiscreteOperator[{"Fourier",1,2^countingQubits},Range[countingQubits]];inverseQuantumFourierTransform=QuantumDiscreteOperator[Inverse[N[quantumFourierTransform["MatrixRepresentation"]]],Range[countingQubits]];finalStates=inverseQuantumFourierTransform[moddedStates];conditionalModularExponentialRules=ResourceFunction["QuantumToMultiwaySystem"][Floor[conditionalModularExponential["MatrixRepresentation"]]];inverseQuantumFourierTransformRules=ResourceFunction["QuantumToMultiwaySystem"][Transpose[PadRight[#,Length[First[initialStates]]]&/@Transpose[PadRight[#,Length[First[initialStates]]]&/@Floor[inverseQuantumFourierTransform["MatrixRepresentation"]]]]];conditionalModularExponentialCompletionRules=ResourceFunction["KnuthBendixCompletion"][conditionalModularExponentialRules,ToString/@convertToProportionalStates[initialStates["StateVector"]],stepCount];inverseQuantumFourierTransformCompletionRules=ResourceFunction["KnuthBendixCompletion"][inverseQuantumFourierTransformRules,ToString/@convertToProportionalStates[moddedStates["StateVector"]],stepCount];{ResourceFunction["MultiwaySystem"][Join[conditionalModularExponentialRules,conditionalModularExponentialCompletionRules],ToString/@convertToProportionalStates[initialStates["StateVector"]],stepCount,rest],ResourceFunction["MultiwaySystem"][Join[inverseQuantumFourierTransformRules,inverseQuantumFourierTransformCompletionRules],ToString/@convertToProportionalStates[moddedStates["StateVector"]],stepCount,rest]}]
Demonstration
Demonstration
In[]:=
MultiwayShorAlgorithm[<|"Number"6,"InitialGuess"7,"CountingQubits"3,"AncillaQubits"2|>,3,"EvolutionGraphStructure","IncludeStateWeights"True,VertexLabels"VertexWeight"]
Out[]=
,
In[]:=
CompletedMultiwayShorAlgorithm[<|"Number"6,"InitialGuess"7,"CountingQubits"3,"AncillaQubits"2|>,2,"EvolutionGraphStructure","IncludeStateWeights"True,VertexLabels"VertexWeight"]
Out[]=
,
In[]:=
EdgeCount[Last@CompletedMultiwayShorAlgorithm[<|"Number"6,"InitialGuess"7,"CountingQubits"3,"AncillaQubits"2|>,2,"EvolutionGraphStructure","IncludeStateWeights"True,VertexLabels"VertexWeight"]]