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.
32 questions
1
vote
1
answer
74
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
119
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
104
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 ...
- 459
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
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
2
votes
1
answer
74
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 ...
- 541
2
votes
3
answers
146
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 ...
- 141
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
2
votes
2
answers
209
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
...
- 159
3
votes
1
answer
115
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
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
5
votes
1
answer
193
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
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
1
vote
1
answer
667
views
Clifford circuit approximation to a random Clifford circuit
Given a random Clifford state on $L$ qubits (defined as an infinite depth Clifford circuit acting on the zero state), what depth Clifford circuit is required to approximate this state to a given ...
- 330
8
votes
1
answer
769
views
Is the Solovay-Kitaev theorem relevant for modern hardware?
The Solovay-Kitaev theorem (and more recent improvements) explains how to efficiently compile any 2-qubit unitary into any universal (dense) finite set of gates. My question is if this theorem is ...
- 1,695
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
4
votes
1
answer
135
views
In Solovay-Kitaev's algorithm, where does the rotation relation $\sin(\theta / 2) = 2 \sin^2(\phi/2)\sqrt{1 - \sin^4(\phi/2)}$ come from?
In Dawson's and Nielsen's pedagogical review of the Solovay-Kitaev algorithm, they describe the decomposition of U into $U=VWV^\dagger W^\dagger$, with both $V, W$ being unitary, being rotated by $\...
- 1,112
4
votes
1
answer
405
views
Error Propagation in quantum gates
When decomposing an arbitrary SU(2) matrix into elements from a universal gate set (i.e. with the Solovay-Kitaev Theorem) we try to get the lowest error possible, which leads to 'chains' of these ...
- 151
6
votes
2
answers
810
views
How can I find a Clifford+T approximation of an arbitrary one qubit gate in Qiskit?
I know the Solovay-Kitaev algorithm can achieve this. Is there an implementation of this or any other algorithm for the same task in Qiskit? Or perhaps some other library that interfaces well with ...
- 857
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
3
votes
1
answer
157
views
a question about quantum gate decomposition on simulator or emulator
I have read a paper about "approximated decomposition" of a unitary single gate (Solovay-Kitaev algorithm) which told us a any unitary single gate can be decomposed into {Hadamard, Phase} with any ...
- 467
1
vote
1
answer
185
views
Understanding the length of the sequence obtained via Solovay-Kitaev decomposition
I have downloaded two codes of SK algorithm from GitHub and try to understand how to decompose a unitary single qubit gate. These code are https://github.com/DEBARGHYA4469/Quantum-Compiler and https:/...
- 467
7
votes
1
answer
313
views
Why is phase gate a member of universal gate set?
According to Solovay-Kitaev theorem it is possible to approximate any unitary quantum gate by sequence of gates from small set of another gates. The approximation can be done with an arbitrary ...
- 14.9k
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
12
votes
1
answer
396
views
Sampling random circuits vs Solovay-Kitaev compiler
Suppose I want to obtain a gate sequence representing a particular 1 qubit unitary matrix.
The gate set is represented by a discrete universal set, e.g. Clifford+T gates or $\{T,H\}$ gates.
A well ...
- 141
4
votes
1
answer
197
views
Rewrite circuit with measurements with unitaries
In quantum physics, because of the no-cloning theorem, lots of classical proofs of cryptographic problems cannot be turned into quantum proofs (rewinding is usually not possible quantumly). A dream ...
- 676
7
votes
1
answer
271
views
Status of software packages for quantum compiling
By "quantum compiling", what I mean is classical algorithms to solve the following problem: given a $SU(D)$ matrix $U$ (the goal) and a set of $SU(D)$ unitary matrices $V_1 \cdots V_N$ (the gates), ...
- 173
13
votes
3
answers
2k
views
Approximating unitary matrices
I currently have 2 unitary matrices that I want to approximate to a good precision with the fewer quantum gates possible.
In my case the two matrices are:
The square root of NOT gate (up to a global ...
- 5,102
7
votes
1
answer
292
views
Does the GLOA have any advantage over the Solovay-Kitaev algorithm?
The Solvay Kitaev algorithm was discovered long before the Group Leaders Optimization algorithm and it has some nice theoretical properties. As far as I understand, both have exactly the same goals: ...
- 17.8k
8
votes
2
answers
732
views
Number of gates required to approximate arbitrary unitaries
If I understand correctly, there must exist unitary operations that can be approximated to a distance $\epsilon$ only by an exponential number of quantum gates and no less.
However, by the Solovay-...
- 1,515
9
votes
1
answer
587
views
Basic approximation in Solovay-Kitaev algorithm
I read the Solovay-Kitaev algorithm for approximation of arbitrary single-qubit unitaries. However, while implementing the algorithm, I got stuck with the basic approximation of depth 0 of the ...
- 185
15
votes
1
answer
480
views
How does approximating gates via universal gates scale with the length of the computation?
I understand that there is a constructive proof that arbitrary gates can be approximated by a finite universal gate set, which is the Solovay–Kitaev Theorem.
However, the approximation introduces an ...
- 2,457