WolframAlpha.com
WolframCloud.com
All Sites & Public Resources...
Products & Services
WolframOne
Mathematica
WolframAlpha Notebook Edition
Programming Lab
Finance Platform
System Modeler
Wolfram Player
Wolfram Engine
WolframScript
Enterprise Private Cloud
Application Server
Enterprise Mathematica
WolframAlpha Appliance
Enterprise Solutions
Corporate Consulting
Technical Consulting
WolframAlpha Business Solutions
Resource System
Data Repository
Neural Net Repository
Function Repository
WolframAlpha
WolframAlpha Pro
Problem Generator
API
Data Drop
Products for Education
Mobile Apps
Wolfram Player
Wolfram Cloud App
WolframAlpha for Mobile
WolframAlphaPowered Apps
Services
Paid Project Support
Wolfram U
Summer Programs
All Products & Services »
Technologies
Wolfram Language
Revolutionary knowledgebased programming language.
Wolfram Cloud
Central infrastructure for Wolfram's cloud products & services.
Wolfram Science
Technologyenabling science of the computational universe.
Wolfram Notebooks
The preeminent environment for any technical workflows.
Wolfram Engine
Software engine implementing the Wolfram Language.
Wolfram Natural Language Understanding System
Knowledgebased broadly deployed natural language.
Wolfram Data Framework
Semantic framework for realworld data.
Wolfram Universal Deployment System
Instant deployment across cloud, desktop, mobile, and more.
Wolfram Knowledgebase
Curated computable knowledge powering WolframAlpha.
All Technologies »
Solutions
Engineering, R&D
Aerospace & Defense
Chemical Engineering
Control Systems
Electrical Engineering
Image Processing
Industrial Engineering
Mechanical Engineering
Operations Research
More...
Finance, Statistics & Business Analysis
Actuarial Sciences
Bioinformatics
Data Science
Econometrics
Financial Risk Management
Statistics
More...
Education
All Solutions for Education
Trends
Machine Learning
Multiparadigm Data Science
Internet of Things
HighPerformance Computing
Hackathons
Software & Web
Software Development
Authoring & Publishing
Interface Development
Web Development
Sciences
Astronomy
Biology
Chemistry
More...
All Solutions »
Learning & Support
Learning
Wolfram Language Documentation
Fast Introduction for Programmers
Wolfram U
Videos & Screencasts
Wolfram Language Introductory Book
Webinars & Training
Summer Programs
Books
Need Help?
Support FAQ
Wolfram Community
Contact Support
Premium Support
Paid Project Support
Technical Consulting
All Learning & Support »
Company
About
Company Background
Wolfram Blog
Events
Contact Us
Work with Us
Careers at Wolfram
Internships
Other Wolfram Language Jobs
Initiatives
Wolfram Foundation
MathWorld
ComputerBased Math
A New Kind of Science
Wolfram Technology for Hackathons
Student Ambassador Program
Wolfram for Startups
Demonstrations Project
Wolfram Innovator Awards
Wolfram + Raspberry Pi
Summer Programs
More...
All Company »
Search
WOLFRAM COMMUNITY
Connect with users of Wolfram technologies to learn, solve problems and share ideas
Join
Sign In
Dashboard
Groups
People
Message Boards
Answer
(
Unmark
)
Mark as an Answer
GROUPS:
Wolfram Science
Computer Science
Physics
Wolfram Language
Wolfram Summer School
Wolfram Fundamental Physics Project
5
Yoav Rabinovich
[WSS20] Shor's Algorithm in Multiway Systems
Yoav Rabinovich
Posted
1 year ago
2422 Views

0 Replies

5 Total Likes
Follow this post

Abstract
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 periodfinding coroutine 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 KnuthBendix 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
m
o
d
N
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
〉
C
M
E

x
,
f
(
x
)
〉
i
Q
F
T
B
i
a
s
e
d
S
u
p
e
r
p
o
s
i
t
i
o
n
M
e
a
s
u
r
e
m
e
n
t
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 subexponential time, making Shor’s algorithm the foremost candidate for demonstrating quantum speedup, and an anticipated application of nearfuture 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:
I
n
[
]
:
=
a
c
t
i
o
n
=
A
s
s
o
c
i
a
t
i
o
n
[
T
a
b
l
e
[
K
e
t
[
i
,
0
]
K
e
t
[
i
,
M
o
d
[
a
^
i
,
N
1
]
]
,
{
i
,
0
,
2
^
q

1
}
]
]
O
u
t
[
]
=

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
〉
,

1
0
,
0
〉

1
0
,
1
〉
,

1
1
,
0
〉

1
1
,
5
〉
,

1
2
,
0
〉

1
2
,
1
〉
,

1
3
,
0
〉

1
3
,
5
〉
,

1
4
,
0
〉

1
4
,
1
〉
,

1
5
,
0
〉

1
5
,
5
〉
The state that results from the iQFT operation then encodes the necessary information for periodfinding.
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:
G
r
a
p
h
P
l
o
t
[
Q
F
T
e
v
o
,
A
s
p
e
c
t
R
a
t
i
o
0
.
2
]
Example multiway system corresponding to the CME operating on a prepared state with nine counting qubits:
I
n
[
]
:
=
G
r
a
p
h
P
l
o
t
[
C
M
E
e
v
o
,
A
s
p
e
c
t
R
a
t
i
o
0
.
2
]
O
u
t
[
]
=
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 KnuthBendix 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:
I
n
[
]
:
=
Q
F
T
c
o
m
p
=
c
o
m
p
a
r
i
s
o
n
[
F
l
o
o
r
[
P
a
d
R
i
g
h
t
[
i
Q
F
T
[
"
M
a
t
r
i
x
R
e
p
r
e
s
e
n
t
a
t
i
o
n
"
]
,
{
2
^
(
q
+
n
)
,
2
^
(
q
+
n
)
}
]
]
,
m
o
d
d
e
d
s
t
a
t
e
s
]
G
r
a
p
h
E
d
g
e
s
:
2
4
4
C
o
m
p
l
e
t
i
o
n
R
u
l
e
s
:
4
0
0
O
u
t
[
]
=
In conclusion, from this preliminary analysis, the complexity of KnuthBendix 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:
I
n
[
]
:
=
G
r
a
p
h
P
l
o
t
[
Q
F
T
e
v
o
]
O
u
t
[
]
=
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/chalgorithms/shor.html#3.QiskitImplementation.
◼
J. Gorard, Some Quantum Mechanical Properties of the Wolfram Model [preprint], retrieved from https://www.wolframcloud.com/obj/wolframphysics/Documents/somequantummechanicalpropertiesofthewolframmodel.pdf.
POSTED BY:
Yoav Rabinovich
Answer
Mark as an Answer
Reply

Flag
Reply to this discussion
in reply to
Add Notebook
Community posts can be styled and formatted using the
Markdown syntax
.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Publish anyway
Cancel
Reply Preview
Attachments
Remove
Add a file to this post
Follow this discussion
or
Discard
Group Abstract
Be respectful. Review our
Community Guidelines
to understand your role and responsibilities.
Community Terms of Use
Feedback
Enable JavaScript to interact with content and submit forms on Wolfram websites.
Learn how »