Shor's algorithm in multiway systems​
​by Yoav Rabinovich
Shor’s algorithm for integer factorization is one of the only candidates in quantum computing for demonstrating polynomial speedup over classical algorithms. In Wolfram models, the measurement process can be described precisely, and potentially support or refute any such speedup under the theory. We implement the period-finding co-routine of Shor’s algorithm in Mathematica’s Quantum Computing framework, and compile it into a multiway system, so that it can be readily analyzed in that lens. We examine the complexity of the Knuth-Bendix completion procedure that corresponds to quantum measurement of Shor’s algorithm in Wolfram models, and compare it to the computational complexity of classical simulation.

Shor’s Algorithm

Shor’s algorithm factors integers by producing plausible ansatz (read: good guess) candidates for number that have common divisors with the target integer.
It achieves this by using a quantum circuit that allows to quickly determine the period
r
of the modulo exponentiation function:
​
​
f(x)=
x
a
modN
​
​
The circuit, once initialized, first performs a conditional Modulo Exponentiation which entangles each
x
with its respective
f(x)
, and then an inverse Quantum Fourier Transform operation to find the period
r
, by interfering the qubits in a way that results in a superposition that is likely to produce states that are multiples of
1/r
when measured.
|x,0〉CME|x,f(x)〉iQFTBiased SuperpositionMeasurement
n
r

With this procedure, Shor’s algorithm runs using an amount of quantum gates polynomial in N, whereas the fastest classical alternative for integer factorization, the general number field sieve, runs only in sub-exponential time, making Shor’s algorithm the foremost candidate for demonstrating quantum speedup, and an anticipated application of near-future quantum computing.

Implementation in Mathematica

For this project, the conditional Modulo Exponentiation (CME) and the inverse Quantum Fourier Transform (iQFT) operators were implemented in Mathematica’s upcoming Quantum Computing framework.
Given parameters
N
(integer to factor),
a
(initial guess),
q
(number of counting qubits) and
n
(number of ancilla qubits), a quantum register is initialized, and the CME and iQFT operators are constructed.
Example action of a CME operator with four counting qubits:
In[]:=
action=Association[Table[Ket[i,0]Ket[i,Mod[a^i,N1]],{i,0,2^q-1}]]
Out[]=
|0,0〉|0,1〉,|1,0〉|1,5〉,|2,0〉|2,1〉,|3,0〉|3,5〉,|4,0〉|4,1〉,|5,0〉|5,5〉,|6,0〉|6,1〉,|7,0〉|7,5〉,|8,0〉|8,1〉,|9,0〉|9,5〉,|10,0〉|10,1〉,|11,0〉|11,5〉,|12,0〉|12,1〉,|13,0〉|13,5〉,|14,0〉|14,1〉,|15,0〉|15,5〉
The state that results from the iQFT operation then encodes the necessary information for period-finding.

Compilation to Multiway Systems

Having defined the quantum operators, we compile their action onto a multiway system where edges connect basis states according to the unitary evolution dictated by the operators. To discretize the Hilbert space in which the states reside, we convert superpositions to proportional collections of nodes, and determine amplitudes or resulting states by counting up incoming edges.
Example multiway system corresponding to the iQFT operating on a prepared state with four counting qubits. Node weights correspond to amplitudes:
Example multiway system corresponding to the CME operating on a prepared state with nine counting qubits:
In[]:=
GraphPlot[CMEevo,AspectRatio0.2]
Out[]=

Measurement Complexity

In Wolfram models, quantum observation corresponds to a foliation of the multiway system which generates apparent causal invariance in the multiway graph. This is possible by using Knuth-Bendix completions to create equivalence between some minimal amount of states in the multiway graph, which is a process that varies in complexity depending on the superposition one requires to resolve. This process therefore has the potential to support or refute the possibility of quantum speedups by adding inherent complexity to the process of measurement in quantum computing.
To evaluate the possibility of quantum speedup in Shor’s algorithm in Wolfram models, we compared the amount of rules added during the completion procedure to the amount of computational steps required to simulate the system classically, for a handful of anecdotal test cases. While the CME operator is causal invariant owing to its classical roots, iQFT is not. In fact. in each comparison, the added rules outweighed the cost of simulation.
Example of comparison between classical simulation complexity and completion cost, for an iQFT operating on a system with 4 counting qubits:
In[]:=
QFTcomp=comparison[Floor[PadRight[iQFT["MatrixRepresentation"],{2^(q+n),2^(q+n)}]],moddedstates]
Graph Edges: 244
Completion Rules: 400
Out[]=
In conclusion, from this preliminary analysis, the complexity of Knuth-Bendix completion of the iQFT operator seems to outweigh the quantum speedup of Shor’s algorithm in Wolfram models.
Example of the action of an iQFT operator on a prepared state with nine counting qubits, enough to factor the integer 6 using Shor’s algorithm:
In[]:=
GraphPlot[QFTevo]
Out[]=

Keywords

◼
  • Quantum Computing
    • ◼
  • Shor’s Algorithm
    • ◼
  • Multiway Systems
    • ◼
  • Wolfram Physics
    • ◼
  • Quantum Measurement
    • ◼
  • Quantum Speedup

    • Acknowledgment

    Mentors: Jack Heimrath, Jonathan Gorard.
    I’d also like to thank Stephen Wolfram and Wolfram Summer School for the opportunity and Professor Kiel Howe for the support.

    References

    ◼
  • Shor’s Algorithm, Qiskit Textbook, retrieved from https://qiskit.org/textbook/ch-algorithms/shor.html#3.-Qiskit-Implementation.
    • ◼
  • J. Gorard, Some Quantum Mechanical Properties of the Wolfram Model [preprint], retrieved from https://www.wolframcloud.com/obj/wolframphysics/Documents/some-quantum-mechanical-properties-of-the-wolfram-model.pdf.