Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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.

Filter by
Sorted by
Tagged with
8
votes
1answer
79 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 ...
4
votes
1answer
86 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 ...
5
votes
1answer
162 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), ...
10
votes
3answers
721 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 ...
6
votes
0answers
121 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: ...
8
votes
2answers
235 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-...
6
votes
1answer
244 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 ...
13
votes
1answer
147 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 ...