Questions tagged [solovay-kitaev-algorithm]
For questions about the Solovay-Kitaev theorem (and algorithm), a proof that quantum computers can efficiently simulate any 1-qubit quantum gate using a restricted set of quantum gates, as well as the generalisation allowing for the efficient creation of gates with some arbitrarily number of dimensions.
35 questions
3 votes
2 answers
80 views
Synthesis of single-qubit rotation in time $O(\log(1/\epsilon))$
Can a gate sequence approximating a given single-qubit rotation up to precision $\epsilon$ be compiled in time $O(\log(1/\epsilon))$ (i.e., time strictly logarithmic and not polylog)?
- 233
3 votes
1 answer
147 views
Isn't the Solovay-Kitaev Algorithm already great for Hamiltonian Simulation?
Reading Andrew Child's lecture notes I've come across the following remark: "There are a few cases where a Hamiltonian can obviously simulated efficiently. For example, this is the case if H only ...
- 141
1 vote
1 answer
137 views
Approximating $n$-qubit Unitaries with Universal Gate Sets
Let $G$ be a universal gate set. Then, for all $\epsilon > 0$, all positive integers $n$, and all $U \in U(2^n)$, there exists an $n$-qubit circuit $Q$ over $G$ such that $\|Q - U\| < \epsilon$. ...
- 601
1 vote
1 answer
156 views
Why does the Solovay-Kitaev theorem use the operator norm?
In this review explaining the Solovay-Kitaev theorem, it is stated that the theorem uses the operator norm to define closeness between unitaries. This is then used to determine if a particular set of ...
- 13
1 vote
1 answer
281 views
Approximate decomposition of general $n$-qubit unitary to universal gate set
The Solovay-Kitaev algorithm claims that any $n$-qubit unitary gate can be decomposed to $O(\log^c(1/\epsilon))$ gates in any given universal gate set, e.g. Clifford+T. However, the number of qubits $...
- 51
1 vote
2 answers
245 views
What's the best way to approximate a unitary $N\times N$ gate by a quantum circuit?
I have a unitary matrix of dimension $N$, and I want to approximate it using a quantum circuit. I know that the Solovay-Kitaev theorem gives an algorithm that takes $2^{O(N^2)}$ steps. Is this the ...
- 489
0 votes
0 answers
106 views
Solovay-Kitaev algorithm with non-constant number of qubits
The Solovay-Kitaev algorithm gives a construction to $\epsilon$-approximate any $m$-qubit unitary $U$ with $O(m \log(m/\epsilon))$ elementary gates, provided $m$ is a constant. My question is: if the ...
- 489
1 vote
0 answers
70 views
How to show that controlled-square-root-of-Z gates and T gates generate all IQP circuits?
The class of instantaneous quantum polynomial (IQP) circuits is an interesting restricted model of quantum computation - circuits running according to the model likely cannot achieve the full scope of ...
- 16.3k
2 votes
1 answer
105 views
Quantum compilation algorithm with respect to other Schatten $p$-norm
In standard quantum compilation algorithms (such as the Solovay-Kitaev theorem), one approximates an arbitrary unitary using words from some universal gate set. The "approximation" here is ...
- 601
2 votes
3 answers
240 views
Seeking Programming Projects and Tools for Quantum Gate Decomposition Implementations
The Solovay-Kitaev theorem shows that "this approximation can be made surprisingly efficient, thereby justifying that quantum computers need only implement a finite number of gates to gain the ...
- 161
6 votes
0 answers
215 views
Can we obfuscate the identity?
Motivated by Aaronson's call to find simple, verifiable proofs of quantumness, suppose we start off with a random polynomial-length circuit $U$ of, say, Hadamard+CCNOT (Toffoli) or CSWAP (Fredkin) ...
- 16.3k
2 votes
2 answers
324 views
Gate synthesis with parametrised precision
I am wondering whether Qiskit (or other quantum program language) can perform gate synthesis with parametrised precision. I tried with ...
- 169
3 votes
1 answer
131 views
Sequence lenght analysis of the Solovay-Kitaev Algorithm
In the paper by Dawson and Nielsen where they develop an algorithm for the Solovay-Kitaev Theorem, they analyze the lenght of the output noting how, for an approximation of degree $n$, the lenght of ...
- 33
2 votes
1 answer
364 views
clarifying a step in the proof of Solovay-Kitaev theorem
There is a step in the proof of the proof of Solovay-Kitaev theorem about the existence of a set containing words of at most length length $l_0$ that cover $SU(2)$ . The proof I'm reading in given in ...
- 321
5 votes
1 answer
268 views
When proving the Solovay-Kitaev theorem, why do we consider a small neighborhood $S_\epsilon$ of the identity?
There are number of points I haven't understood or am confused in the proof of Solovay-Kitaev theorem. The proof I'm reading in given in the Appendix 3 of Neilson and Chuang's book, Quantum ...
- 321