Questions tagged [gate-synthesis]

For questions about finding (short) gate sequences to implement a specific unitary operation, for example decomposing a complicated multi-qubit gate into a sequence of basic gates. It might apply to optimizing circuits with respect to length or depth or finding gate sequences to implement an algorithm.

Filter by
Sorted by
Tagged with
5 votes
2 answers
52 views

What's the most efficient decomposition in terms of T-count of the 4-qubit Toffoli with 1 ancilla?

When decomposing the 4-qubit Toffoli in the Clifford+T universal gate set with 1 ancilla qubit, what is the most efficient implementation one can get in terms of T-count? I can only find papers that ...
  • 53
0 votes
0 answers
23 views

Translate a sparse matrix into a products of elementary gates

I want to construct a parametrized gate whose matrix representation has many zero elements. Are there any known recipes to construct such a gate from elementary gates (Pauli rotations, CNOT, etc.)?
  • 1
1 vote
1 answer
40 views

How to synthesize function $f(x)$ in amplitude encoding

In computational basis encoding, the way to encode $f(x)$ is known - a classical circuit is converted to a quantum circuit which takes $|x\rangle|0\rangle \to |x\rangle|f(x)\rangle $. I wonder how I ...
0 votes
1 answer
40 views

Implementing Odd Permutations Without Ancilla Bit

The paper says that The inversion $\alpha \mapsto \alpha^{-1} $ (where 0 is mapped to 0) can be seen as a permutation on $\mathbb F_{256}$. This permutation is odd, while quantum circuits with NOT, ...
  • 1
3 votes
1 answer
101 views

Cirq : Reference for Toffoli decomposition

I was trying to find a reference for the 7 T-gate decomposition of the Toffoli gate given by Cirq. The decomposition originates from the the one used for CCZPowGate as given in the doc string here ...
0 votes
0 answers
26 views

Minimal decomposition for a 4 qubit QFT in a Superconducting architecture

i'm looking for a minimal decomposition in terms of Cnot for the 4 qubit QFT circuit in the 7 qubit architecture reported in figure. I'm using qubits 0,2,4,6 as ancillas for my QPE algorithm. The ...
1 vote
0 answers
103 views

PyZX optimisation steps for Clifford circuits

Given the following ZX-diagram It should represent some random Clifford circuit (LC means Local Clifford). As far as I got, any Clifford circuit can be transformed into a ZX-diagram like the above, i....
1 vote
3 answers
104 views

How to decompose a multi qubit Clifford unitary into a sequence of clifford gates

What are the algorithms that allow to decompose any given multi qubit Clifford unitary into elementary Clifford operations (e.g. Pauli+CNOT, with no T gate)?
1 vote
0 answers
62 views

Faithful description of a photonic setting with the circuit model

The above picture comes from this paper. The circuit on the left and the one on the right are equivalent (up to the basis). However, there is an important difference: the circuit makes the input -- i....
2 votes
2 answers
359 views

Does phase kickback require the system to be in the eigenstate?

I've been watching this video for the introduction to phase kickback. And here's a diagram: I got confused if we really need $|\psi_k\rangle$ to be an eigenstate to make the kickback work. It seems ...
  • 317
1 vote
1 answer
120 views

Best implementation for logical CNOT on Shor's code?

As the Shor's code is a CSS code, it admits a transversal implementation of logical CNOT. An immediate implementation may perform 9 (reversed) CNOT, by respecting the order of the qubits. However. ...
2 votes
1 answer
58 views

How to initialize a state of the form$\frac{1}{\sqrt{2}}(|\texttt{++}\rangle + |\texttt{--}\rangle$) in the circuit model?

I wonder how to initialise a Bell-like state, in the circuit model, where instead of standard $|\Phi^{\texttt{+}}\rangle$, the entanglement is in the x-basis. Hence a state $\frac{1}{\sqrt{2}}(|\...
3 votes
2 answers
206 views

On the photonic implementation of Shor's code

The above picture comes from this paper. I can see that the standard Shor's code has been re-designed. I have two main doubts: I can't figure out in figure (b) how the setting inputs the state $\...
0 votes
1 answer
69 views

When are the following equivalences correct?

I can't figure out how the equivalences in the picture hold. The picture comes from this recent publication on PRA. EDIT: I think I might have been mislead by the gate represenation. In fact, the gate ...
2 votes
1 answer
72 views

Is there a name for a gate that 'moves' one qubit to a new position via multiple SWAP gates?

Let's say there is a qubit at position $i$, and I want to move it to position $i'$. Without loss of generality, let's say $i < i'$. By 'move it' I mean, perform multiple $SWAP$ operations so that ...
1 vote
1 answer
46 views

CNOT chain vs CNOT fountain in qiskit

I was going through qiskit's synthesis module, their methods take an argument called cx_structure which has two possible values, ...
2 votes
0 answers
27 views

Techniques to parallelize controlled-unitaries controlled by the same qubit but acting on different target qubits

I need to find a way to parallelize a set of controlled-unitaries that are all controlled by the same qubit and are targetting $n$ different qubits. The main constraint that I have is that I can only ...
3 votes
0 answers
79 views

What is the correct name of this quantum gate? Possibly state control gate

Let $\vec v \in \mathbb{C}^2 $ be the following quantum state: $$ \vec v = \frac{1}{\sqrt{2}}\begin{bmatrix} v_{1} \\ v_{2} \\ \end{bmatrix},\space \lvert v_1 \rvert = 1,...
5 votes
1 answer
150 views

Construction of unitary matrices built from linear combination of Pauli strings

Let's define $P_k \in \{ I, X, Y, Z \}^{\otimes n}$ and called each of these $P_k$ as a Pauli string (or word) then given that $$U = \sum_{k=1}^L c_kP_k $$ with the following conditions: $\sum_{k=1}...
  • 12.8k
4 votes
1 answer
144 views

If $A^4=B^4=AB=I$, what is a good circuit for $\sqrt A\sqrt B$?

TL/DR What is a good circuit for: $$\frac{1}{2}\begin{pmatrix} -i & i & 1 & 1 \\ 1 & 1 & -i & i \\ i & -i & 1 & 1 \\ 1 & 1 & i & -i\end{...
  • 7,921
2 votes
0 answers
58 views

Creating a unitary for binary encoding with respect to already encoded index states

Let us say that there are two quantum registers qr1 and qr2. Now the qr1 is in the state $\sum_i |x_i\rangle$(here $x_i$ is binary encoded value upto some precision) and originally qr2 is $|0\rangle$, ...
3 votes
1 answer
267 views

How to perform a controlled Pauli string rotation gate?

I would like to know some circuit decomposition for an arbitrary controlled Pauli string rotation: \begin{equation} |0\rangle\langle 0| \otimes e^{i \theta (P_1\otimes...\otimes P_n)}+ |1\rangle\...
  • 421
3 votes
0 answers
80 views

Relation between geometric and discrete circuit complexity

Geometric complexity of a unitary, as introduced for example here https://arxiv.org/abs/quant-ph/0502070, measures the length of a geodesic connecting the identity matrix and a given unitary in the ...
5 votes
1 answer
96 views

Native Gate Decomposition

TL;DR: I've got a very small set of gates to use and need to find efficient decompositions for $R_y$ and controlled $R_y$ gates. Does anyone have any better ideas than what I have? I'm looking to ...
4 votes
1 answer
75 views

Confusion with the number of CNOTs in a circuit

I am a bit puzzled on the following circuit. According to this Quantum Computing SE thread it holds that $$ e^{i(Z\otimes Z)t} = {\rm CNOT} (I\otimes e^{iZt}){\rm CNOT} \qquad (1) $$ As a result we ...
5 votes
2 answers
136 views

How many quantum gates are needed to prepare an arbitrary state?

In this paper there is this sentence: [...] the description of a $2^n\times2^n$ unitary matrix $U$ (which is a poly($n$)-size quantum circuit) According to the meaning of "which" in ...
2 votes
1 answer
64 views

Decompose bell measurement gate into combination of controlled-not gates and one-qubit gates

OPENQASM2.0 has only one two-qubit gate: controlled not. For a teleportation experiment, I need to perform a measurement in the Bell basis. That is, I need a two-qubit gate with matrix representation $...
7 votes
1 answer
413 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 vote
2 answers
47 views

Circuit including phase factor in $XY(\beta, \theta)$ gate

In Implementation of the XY interaction family with calibration of a single pulse, the $XY(\beta, \theta)$ gate is defined as $$ XY(\beta, \theta) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 &...
  • 2,655
-2 votes
1 answer
88 views

Decomposition of U1 gate $U_1(\lambda)$ , Phase Shift gate $\phi(\delta) $, and Swap gate [closed]

Can we express U1 gate $U_1(\lambda)$ , Phase Shift gate $\phi(\delta) $, and Swap gate $$ U_1(\lambda) = \begin{pmatrix}1 & 0 \\ 0 & e^{i\lambda}\end{pmatrix}$$ $$ \phi(\delta) = \begin{...
  • 183
3 votes
2 answers
81 views

Optimal decompositions of some standard multi-qubit gates

To have a concrete example in mind: 3-qubit Toffoli gate can be decomposed into 6 $CNOT$s as shown here I believe this is the most economic decomposition in terms of the number of $CNOT$s used. My ...
2 votes
4 answers
628 views

How is a Toffoli gate built without using T gates?

Can someone tell me how to make a Toffoli gate without using T gates? Can we use $R_x$ and $R_y$. If yes, then how? I tried many circuits but I was unable to create the CCNOT gate out of $R_x$, $R_y$ ...
2 votes
1 answer
62 views

Is it possible to decompose $\land(UXU^\dagger)$ in one-qubit operations and only a single $\land(X)$?

Let $U,V$ being any unitary. Is it possible to decompose $\land(UXU^\dagger)$ in one-qubit operations and only a single $\land(X)$? Something like the following: $\land(UXU^\dagger) \equiv (\mathbb{I}\...
1 vote
1 answer
44 views

Generalized push for $\land_{ab}(X)$ gate

EDIT: In the following I am using the Feynman notation for controlled operations - e.g. $\land_{ab}(X)$ is equivalent to a $CNOT$ with control qubit $q_a$ and target $q_b$. Ultimately, for any single-...
4 votes
0 answers
81 views

Universality for reversible classical computation

Is there any way to check whether a set of gates (for example, take the set comprising of the CNOT gate and the Hadamard gate) is universal for reversible classical computation? I can think of trial ...
3 votes
2 answers
166 views

Is it possible to push back an $H$ gate to a $CZ$ gate?

Given the above scenario. Is it possible to "push back" the $H$ gate operation to occur before $CZ$? Formally I am looking for some operation $CZ\cdot(U_1\otimes U_2) = H\cdot CZ$.
3 votes
0 answers
82 views

How exactly does the QuantumCircuit.decompose() method work?

From what I can understand from the source code, the circuit is converted into a DAG before the decomposition transpiler is performed onto the DAG circuit. How does converting to a DAG circuit help us ...
  • 83
7 votes
2 answers
337 views

Complexity of $n$-Toffoli with phase difference

I'm interested in the $n$-Toffoli gates with phase differences. I found a quadratic technique in section 7.2 of this paper. Here's the front page of the paper. Here's an image of the section that I'm ...
  • 101
6 votes
2 answers
2k views

How to visualize Hadamard gate as $X$-$Z$-$X$ decomposition?

In the book Quantum Computation and Quantum Information by Nielsen and Chuang, chapter 4, exercise 4.4 (pg. 175), the author has asked to express Hadamard gate as product of $R_x$, $R_z$ rotations and ...
5 votes
2 answers
222 views

How to implement the power of a product of quantum gates as a circuit?

Suppose I have quantum gates (i.e. unitary matrices) $A$ and $B$, and I want to implement $(AB)^x$ in a circuit. If $x$ is integer, I can simply apply $A B$ repeatedly $x$-times. But what if $x$ is a ...
  • 2,363
6 votes
1 answer
626 views

Transpilation into custom gate set in qiskit

In qiskit, I can transpile a given circuit into a some predefined gate set as follows (just an example) ...
3 votes
0 answers
70 views

Reducing an ansatz to a shallower circuit

Given a very general hardware efficient ansatz as in Figure: and say that you already know all the rotation parameter for the gates in the red box, is there any way to build a gate sequence that ...
  • 433
3 votes
1 answer
254 views

How to create CNOT from an entangling gate and arbitrary single-qubit gates?

I am working on the classical simulation of quantum circuits. I know how to efficiently implement the following entangling gate, which -- in the following paper: https://arxiv.org/pdf/1803.02118 -- ...
4 votes
2 answers
150 views

What gate should one use to perform $R_y$ using a single $R_z$ + Clifford gates?

I know how to perform Rz rotations with the least amount of T gates, eg by using Efficient Clifford+T approximation of single-qubit operators by Peter Selinger. Similarly, one could use H Rz H to ...
  • 421
3 votes
1 answer
79 views

Tool to verify $CNOT$ (or any interacting 2-qubit gate)

Is there any tool to define a circuit and verify if it works as desired? It would be interesting to find ways of performing interacting gates - e.g. CNOT gate - between non adjacent qubits. Hence I'd ...
7 votes
3 answers
880 views

Is it possible to make a Toffoli gate using only CNOTS and ancillas?

I have tried to make a Toffoli gate using only CNOTs and some ancilla qubits but I do not get the unitary. It seems it is not possible without additional gates? What could I do to prove it? I have ...
  • 1,584
2 votes
1 answer
64 views

Do we need to use an ancillary qubit when decomposing arbitrary $U(2^n)$ gates using Clifford+T universal gate sets?

As I know, we can decompose $U$ without ancilla if it's from special unitary group $SU(2^n)$. Do we need to use ancilla qubit on decomposing arbitrary $n$-qubit $U$ using Clifford+T universal gates ...
4 votes
1 answer
299 views

What is Qiskit's Transpiler method for unitary synthesis?

As I could found in here how the transpile works in qiskit, I understood that transpile gets arbitrary Unitary gate $U$ and some set of basis gates as input, and produce some quantum circuit of $U$ ...
3 votes
1 answer
106 views

From mathematical notation to quantum circuit, in general

I am learning the basics of quantum computing using Qiskit and I encountered a problem when I tried to solve some of our course exercises. I feel like I am missing an invisible step, the step from ...
2 votes
3 answers
156 views

Find unitary such that $U:|i\rangle|0\rangle\rightarrow|i\rangle|A_i\rangle$

Let's assume I have two qubits of state $|A_0\rangle$ and $|A_1\rangle$ correspondingly stored in a quantum memory. How do I find a Unitary $U$ that acts on another register of 2-qubits such that $$U:|...
  • 249