12 votes
Accepted

Is the Solovay-Kitaev theorem relevant for modern hardware?

I think you'll find that most hardware, at the hardware level, gives you arbitrary single qubit rotations. So, in that sense, it is true that Solovay-Kitaev is not directly applicable to current ...
DaftWullie's user avatar
10 votes
Accepted

How does approximating gates via universal gates scale with the length of the computation?

Throughout this answer, the norm of a matrix $A$, $\left\lVert A\right\rVert$ will be taken to be the spectral norm of $A$ (that is, the largest singular value of $A$). The solovay-Kitaev theorem ...
Mithrandir24601's user avatar
  • 3,686
10 votes
Accepted

Approximating unitary matrices

You have picked two particularly simple matrices to implement. The first operation (G) is just the square root of X gate (up to global phase): In your gate set, this is $R_X(\pi/2)$. The second ...
Craig Gidney's user avatar
  • 36.7k
9 votes

Sampling random circuits vs Solovay-Kitaev compiler

The Solovay-Kitaev algorithm is not practical. It is very useful theoretically because it proves that once you have a "dense" set of quantum gates (i.e. a set with which you can approximate any other ...
Adrien Suau's user avatar
  • 4,927
7 votes

Approximating unitary matrices

When a two qubit gate $W$ can be expressed (up to a global phase) in the computational basis by a matrix with entirely real entries, i.e., $W \in O(4)$, then there is general construction of ...
David Bar Moshe's user avatar
6 votes
Accepted

Status of software packages for quantum compiling

For Qiskit, there are two tools you can check out. The two qubit kak tool does exactly what you want for 2 qubits. If you give it a two qubit unitary, it gives you a list of gates to realize this, ...
James Wootton's user avatar
5 votes
Accepted

Why is phase gate a member of universal gate set?

You might want a small set of gates, but it doesn't necessarily mean that you want the smallest set possible. When you talk about a fault-tolerant quantum computer, what you really want to do is ...
DaftWullie's user avatar
5 votes
Accepted

How can I find a Clifford+T approximation of an arbitrary one qubit gate in Qiskit?

On the Qiskit front, a Solovay-Kitaev algorithm implementation is on its way https://github.com/Qiskit/qiskit-terra/pull/5657. If you want to use or have a look to this ...
luciano's user avatar
  • 5,763
5 votes
Accepted

Basic approximation in Solovay-Kitaev algorithm

I don't pretend that this is optimal in the sense of minimal number of applications, but here's one method that comes from the universality proof... The unitary that you want to implement can be ...
DaftWullie's user avatar
4 votes

Approximating unitary matrices

Neither of these gates require approximate sequences. You can implement them exactly with your specified gate sets with no great effort. Up to a global phase (which should be irrelevant), G is simply ...
DaftWullie's user avatar
4 votes
Accepted

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?

This simply comes from equation an arbitrary rotation $R_{n}(\theta)$ with the rotation $$ U=R_X(\phi)R_Y(\phi)R_X(-\phi)R_Y(-\phi). $$ The way that I did this calculation, just to verify this claim, ...
DaftWullie's user avatar
4 votes
Accepted

Understanding the length of the sequence obtained via Solovay-Kitaev decomposition

According to the paper The Solovay-Kitaev algorithm (pg. 7) a number of single qubits gates approximating unitary $U$ is $$ l = O(\ln^{\ln5/\ln(3/2)}\frac{1}{\epsilon}), $$ where ${\ln5/\ln(3/2)} = ...
Martin Vesely's user avatar
3 votes

What's the best way to approximate a unitary $N\times N$ gate by a quantum circuit?

I'm not sure where you are getting an exponential number of steps. Let $\mathcal{G}$ be a finite set of generators for $SU(N)$ that is closed under inverses. The Solovay-Kitaev theorem says that for ...
Condo's user avatar
  • 2,008
3 votes
Accepted

Quantum compilation algorithm with respect to other Shatten $p$-norm

Yes, you get the same behavior. This is because all norms on finite dimensional spaces are equivalent. That means that for every $p$ there exist constants $c_p, d_p > 0$ such that $$ d_p \|X\|_p \...
Rammus's user avatar
  • 5,743
3 votes
Accepted

Clifford circuit approximation to a random Clifford circuit

Clifford operations are discrete. They can't approximate arbitrary states. The state may not be close to a state reachable by Clifford operations. There are $O(L^2)$ distinct $L$-qubit states ...
Craig Gidney's user avatar
  • 36.7k
3 votes
Accepted

a question about quantum gate decomposition on simulator or emulator

The restricted gate set of, for example, $\{H,T\}$, is more relevant when you start talking about error corrected quantum computation. It may be that when you act on individual, physical, qubits, you ...
DaftWullie's user avatar
2 votes

Number of gates required to approximate arbitrary unitaries

Note that Solovay-Kitaev theorem holds for unitaries on qu$d$it (section 5 in DN05), then we can set $d=2^n$ for $n$-qubit unitary. Following the same analysis, we obtain length of gate sequences $l_{...
Yupan Liu's user avatar
  • 488
2 votes

Rewrite circuit with measurements with unitaries

Here's a silly method that works if you know $y$, you know the probability of measuring $y$, and you can efficiently generate arbitrary-size superpositions of the form $$\frac{1}{\sqrt{N}}\sum_{b <...
Sam Jaques's user avatar
  • 2,024
2 votes

Gate synthesis with parametrised precision

The "method accepting an arbitrary gate" is a tricky part". There are methods with some set of gates that you might have to later translate with a further transpiler pass. For the ...
luciano's user avatar
  • 5,763
2 votes
Accepted

Sequence lenght analysis of the Solovay-Kitaev Algorithm

They use the rule of conversion of logarithms: $$ \log_b x = \frac{\log_c x}{\log_c b}.$$ For clarity define the following quantity: $$ A:= \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \...
MonteNero's user avatar
  • 2,481
2 votes

When proving the Solovay-Kitaev theorem, why do we consider a small neighborhood $S_\epsilon$ of the identity?

I don't have the book in front of me right now to recall all the details. However, the key point is that if you have a small neighbourhood around identity that you can "hit" with some ...
DaftWullie's user avatar
2 votes

Seeking Programming Projects and Tools for Quantum Gate Decomposition Implementations

First off, the question itself is disparate. You need some version of the Solovay-Kitaev theorem for optimizing a sub-circuit that acts on a single qubit, and you can also use it for two or three ...
Greg Kuperberg's user avatar
1 vote

What's the best way to approximate a unitary $N\times N$ gate by a quantum circuit?

A line of research might be, if you have a way to write your unitary as $U = e^{A}$ for some complex matrix $A$. Then you can use the Lie-Trotter or Suzuki-Trotter decomposition to approximate your ...
baptistechev's user avatar
1 vote

Seeking Programming Projects and Tools for Quantum Gate Decomposition Implementations

It has been a long time (>4 years) since the last time I looked at this code, but I implemented a working version of the Solovay-Kitaev algorithm back then. You will be able to find it in https://...
Adrien Suau's user avatar
  • 4,927
1 vote

Seeking Programming Projects and Tools for Quantum Gate Decomposition Implementations

This certainly depends on what one is attempting to do, ie the algorithm or unitary that one is attempting to implement, and the target basis state (along with understanding precision thresholds and ...
raeth's user avatar
  • 51
1 vote

Error Propagation in quantum gates

Usually, you use such a finite gate set in a fault tolerant scenario, acting on logical qubits. If you're working with physical qubits, you can often make the single-qubit gate directly. But in the ...
DaftWullie's user avatar
1 vote

Does the GLOA have any advantage over the Solovay-Kitaev algorithm?

It sounds like GLOA algorithms are a type of genetic algorithm. Genetic algorithms are heuristic algorithms which often do not have any specified time complexity nor accuracy (which is likely why you ...
Condo's user avatar
  • 2,008
1 vote

Number of gates required to approximate arbitrary unitaries

The full scaling will be $O(4^n\text{poly}\left(\log\frac{1}{\epsilon}\right))$, so you do indeed get exponential scaling in the number of qubits.
Will's user avatar
  • 253

Only top scored, non community-wiki answers of a minimum length are eligible