Implement "standard" quantum algorithms in snippets (Deutsch-Josza, Grover, Shor, etc.)
- 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