WolframAlpha.com
WolframCloud.com
All Sites & Public Resources...
Products & Services
Wolfram|One
Mathematica
Wolfram|Alpha Notebook Edition
Programming Lab
Finance Platform
SystemModeler
Wolfram Player
Wolfram Engine
WolframScript
Enterprise Private Cloud
Enterprise Mathematica
Wolfram|Alpha Appliance
Enterprise Solutions
Corporate Consulting
Technical Consulting
Wolfram|Alpha Business Solutions
Resource System
Data Repository
Neural Net Repository
Function Repository
Wolfram|Alpha
Wolfram|Alpha Pro
Problem Generator
API
Data Drop
Products for Education
Mobile Apps
Wolfram Player
Wolfram Cloud App
Wolfram|Alpha for Mobile
Wolfram|Alpha-Powered Apps
Services
Paid Project Support
Wolfram U
Summer Programs
All Products & Services »
Technologies
Wolfram Language
Revolutionary knowledge-based programming language.
Wolfram Cloud
Central infrastructure for Wolfram's cloud products & services.
Wolfram Science
Technology-enabling 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
Knowledge-based broadly deployed natural language.
Wolfram Data Framework
Semantic framework for real-world data.
Wolfram Universal Deployment System
Instant deployment across cloud, desktop, mobile, and more.
Wolfram Knowledgebase
Curated computable knowledge powering Wolfram|Alpha.
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
High-Performance 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
Computer-Based 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
5
Yoav Rabinovich
[WSS20] Shor's Algorithm in Multiway Systems
Yoav Rabinovich
Posted
9 months ago
1614 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 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
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 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:
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
}
]
]
I
n
[
]
:
=
|
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
〉
O
u
t
[
]
=
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:
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:
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
]
I
n
[
]
:
=
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 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:
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
]
I
n
[
]
:
=
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 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:
G
r
a
p
h
P
l
o
t
[
Q
F
T
e
v
o
]
I
n
[
]
:
=
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/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.
◼
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 »