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.
8 questions with no upvoted or accepted answers
6
votes
0
answers
181
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) ...
- 14.4k
6
votes
0
answers
251
views
Solovay-Kitaev Balanced Group Commutators in SU(2) Implementation
I am currently looking into quantum compilation and came across Dawson and Nielsen's paper on the Solovay-Kitaev Algorithm, which seems like a good starting point as it is referenced in a many of the ...
- 61
5
votes
0
answers
185
views
Is there an analog for the Solovay-Kitaev Theorem for approximating quantum states?
The Solovay-Kitaev theorem shows that we can approximate arbitrary unitary transformations with polynomially many quantum gates. Can we approximate the resulting state vectors in the same way by ...
- 167
4
votes
0
answers
81
views
Fowler Distance in Solovay-Kitaev Algorithm
I have been using this code to implement the Solovay-Kitaev algorithm for approximating arbitrary single qubit gates. One measure of success it gives is the 'Fowler distance'. I cant find a definition ...
- 151
2
votes
0
answers
68
views
Approximating the concatenation of two approximate circuits
Suppose I have two quantum circuits $A_n,B_n$ that I have already found to approximate the operations $U,V$ within some error $\epsilon_n$ and each with an overall circuit depth $\ell_n$ using $n$ ...
- 71
2
votes
1
answer
277
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
1
vote
0
answers
48
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 ...
- 14.4k
0
votes
0
answers
52
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 ...
- 459