fwcd / fwcd/swift-quantum

Implement "standard" quantum algorithms in snippets (Deutsch-Josza, Grover, Shor, etc.)

Open
#2 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Swift
Stars
1
Forks
0
PR merge metrics
No merged PRs in 30d

Description

Would be nice to have some specific examples to illustrate how quantum computations can be used to factor numbers. A non-exhaustive list of such algorithms would be:

- [x] Deutsch-Josza

Problem: Determine whether a given function $f: \\{0, 1\\}^n \to \\{0, 1\\}$ is constant or balanced.

A function $f$ is...

- _constant_ iff $|\\{f(j) \mid j\\}| = 1$
- _balanced_ iff $|\\{j \mid f(j) = 0\\}| = |\\{j \mid f(j) = 1\\}|$.

Note: In all non-trivial cases ($n > 0$) it cannot be both.

- [x] Grover

Problem: Find the solution $a$ to a unique function $f: \\{0, 1\\}^n \to \\{0, 1\\}$.

A function $f$ is _unique_ if $f(a) = 1$ for one specific $a \in \\{0, 1\\}^n$ (which we call the _solution_) and $f(b) = 0$ for all $b \neq a$.

- [ ] Simon

Problem: Find the period of a $\oplus$-periodic (two-to-one) function $f: \\{0, 1\\}^n \to \\{0, 1\\}^{n - 1}$.

A function is $\oplus$_-periodic_ (or _XOR-periodic_) iff $f(b) = f(b') \iff b' \in \\{b, b \oplus a\\}$ for some fixed $a \\in \\{0, 1\\}^n$ (the _period_) and all $b, b' \in \\{0, 1\\}^n$. Intuitively this means that every output maps to exactly two inputs that differ only in the period.

- [ ] Shor

Problem: Find a non-trivial factor of an integer $n > 2$.

The quantum part is slightly more general and finds the period to an arbitrary function (with a certain probability), thus can also be used to solve other problems (e.g. discrete logarithms, which are of interest to "break" other kinds of cryptography). We won't discuss those in detail, but it is useful to keep in mind that the quantum part is only about period finding and not about factoring per se.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reviewing the existing quantum algorithm snippets and the completed Deutsch-Josza and Grover examples to understand their structure. Implement snippets for Simon and Shor based on the problem statements in this issue, and consider the listed period-finding relationship when defining scope. Done means the unchecked algorithms have corresponding examples alongside the completed ones.

Written by the indexing model from the issue text.

Assessment

Tech stack
swift
Domain
quantum-computing
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.