Skip to main content
16 votes
Accepted

Does the Quantum Fourier Transform require universality?

Yes, the QFT requires universality. No, there isn't a non-universal gate set that implements the QFT. Just having the QFT as an operation is already computationally universal, because it can generate ...
Craig Gidney's user avatar
  • 37.1k
8 votes

How are quantum algorithms devised?

Many people having given a lot of thought about these kinds of questions - I really like Aharanov's discussion in a Qiskit article here. Recalling some history, we may have: Feynman took a guess that ...
6 votes
Accepted

How to simulate low-rank hamiltonian?

Let's assume that we know the circuit $V$ the constructs $|u\rangle$, i.e. $$ V|0\rangle=|u\rangle. $$ So, this reduces our problem to creating the evolution $$ V^\dagger UV=e^{-it|0\rangle\langle 0|}....
DaftWullie's user avatar
  • 58.2k
5 votes
Accepted

Is the plus state a magic state for the Hadamard gate?

Start with a state $|\psi\rangle|+\rangle$. Measure the operator $X_1Z_2$ using either lattice surgery or an ancilla qubit and $CZ,CX$ gates. Call this result $m_{xz}$ Then measure the first qubit in ...
Jahan Claes's user avatar
5 votes
Accepted

How to come up with Simon's Algorithm circuit for this 3 qubit system? (given truth table & s)

I'm not saying this is a good way of doing it, but if you're completely stumped, there is always a fallback: use a multi-controlled-not. For example, if you use controlled-controlled-controlled-not, ...
DaftWullie's user avatar
  • 58.2k
5 votes
Accepted

Given $f: \{0, 1\}^n\to\{0, 1\}^m$, how many qubits are needed to implement the oracle $\mathcal U|x,0\rangle^{\otimes m}=|x,f(x)\rangle$?

Usually, saying that there is access to an oracle compute $f$ is equivalence to saying that you assume a model in which it is given that $f$ can be computed for free, Namely, In your case $f :\{0,1\}^...
Dudu Ponar's user avatar
5 votes

Why isn't $Ry(\pi/2)$ gate equivalent to Hadamard gate?

The algebraic comparison of the operations is, of course, correct. Additionaly, noting that $H$ is Hermitian, we see that $R_y\left(\frac{\pi}{2}\right)$ is not Hermitian, and must be transformed. A ...
inq's user avatar
  • 111
5 votes
Accepted

Qiskit reverse_bits is not equivalent to swapping qubits

The issue is that the qubit values are being mixed together throughout the circuit, so swapping at the end is not enough. However, if you also swap at the beginning of the circuit, the qubit values ...
Nick Mertes's user avatar
5 votes
Accepted

Which qubit has the highest $|1\rangle$ amplitude?

TL;DR: Single-shot circuit of this sort would enable FTL comms, so is not possible. Multiple-shot variant can be realized using for example Quantum State Tomography or (more efficiently) Direct ...
Adam Zalcman's user avatar
  • 22.5k
5 votes
Accepted

How to construct a quantum circuit for quantum Fourier transform in a prime dimensional Hilbert space?

This is covered in the paper "Exact quantum Fourier transforms and discrete logarithm algorithms": We show how the quantum fast Fourier transform (QFFT) can be made exact for arbitrary ...
Craig Gidney's user avatar
  • 37.1k
5 votes
Accepted

Is it possible to modify the QFT circuit to use only 1-qubit gates?

This is called qubit recycling (when combined with introducing the qubits-to-QFT one by one). All you have to do is take the normal circuit, measure each qubit immediately after it gets Hadamard'ed, ...
Craig Gidney's user avatar
  • 37.1k
4 votes

When running an arbitrary quantum circuit, can all of the entanglement be done up front?

Yes. What you are looking for is called Measurement-based quantum computing, also called one-way quantum computing. The wikipedia page is quite instructive https://en.wikipedia.org/wiki/One-...
Abdullah Khalid's user avatar
4 votes

How to express Hadamard gate as a generic trigonometric functions of theta?

In the first case, the gate operates by the mapping $H|1\rangle = \cos\theta|0\rangle - \sin\theta|1\rangle$. The second by $H|1\rangle = -\sin\theta|0\rangle + \cos\theta|1\rangle$. What is the ...
Abdullah Khalid's user avatar
4 votes
Accepted

Can the oracle for $f:\{0,1\}^n \rightarrow \{0,1\}^m$ be implemented with only $n+m$ qubits?

Your argument is correct, but needs to be made with a little care. The way that a universality proof often goes is that you decompose the target unitary into a series of Givens rotations. Each such ...
DaftWullie's user avatar
  • 58.2k
4 votes
Accepted

How to implement projective measurement from multiple measurements?

The point of the second register is to initialize it in some state with an equal probability of being found in any basis state $|i\rangle$. Then, conditioned on the state of the second register, one ...
Quantum Mechanic's user avatar
4 votes

Map $n$ qubit state with complex amplitudes to $n+1$ qubit state with real amplitudes

Call the operation you want to construct $D$ and call the qubit that ends up storing the real/imaginary distinction $q$. If I gave you $D$, you could apply $D$ then $Z_q$ then $D^{-1}$. The overall ...
Craig Gidney's user avatar
  • 37.1k
4 votes
Accepted

Is it possible to implement the controlled-S gate, such that the inner gate between the CNOTs belongs to the Clifford?

TL;DR: After sending $D$ across the equals sign, the right hand side is similar to a controlled Pauli operator and the left hand side is a diagonal operator. Their spectra turn out to be incompatible, ...
Adam Zalcman's user avatar
  • 22.5k
3 votes

Superposition on a subset of integers

Perhaps the easiest way is to find $n=\lceil\log_2(k+1)\rceil$. Take $n$ qubits in the state $|0\rangle$ and apply Hadamard to each of them. If $k+1$ was a power of 2, you're done! If not, get an ...
DaftWullie's user avatar
  • 58.2k
3 votes

Are there low T-count measurement and Clifford correction protocols for diagonal CNOT+T gates other than CCZ?

My intuition is that ancilla qubits and feedback are almost always useful for reducing T count. Pick any gate, and preventing yourself from using workspace will make it less efficient to implement. ...
Craig Gidney's user avatar
  • 37.1k
3 votes
Accepted

How to construct a two-qubit circuit implementing the oracle for Simon's algorithm, in qiskit?

In Simon's algorithm, the oracle maps $|0\rangle|x\rangle$ to $|f(x)\rangle|x\rangle$. In your case: $$|00\rangle|00\rangle \rightarrow |10\rangle|00\rangle$$ $$|00\rangle|01\rangle \rightarrow |10\...
Egretta.Thula's user avatar
3 votes
Accepted

Calculating the classical OR gate in a 3 qubit (+1 ancillary qubit) circuit

There are two errors in your code: You only initialize the first two bits, the last bit of the input is unused. Thus, you should replace: ...
Tristan Nemoz's user avatar
  • 6,162
3 votes

How to convert a simple matrix into circuit?

In qiskit, you can run the following code: ...
Saksham's user avatar
  • 47
3 votes

Map $n$ qubit state with complex amplitudes to $n+1$ qubit state with real amplitudes

This will violate unitarity of the transformation $U$. Consider states $$\begin{bmatrix}\frac1{\sqrt2} \\ \frac1{\sqrt2}\end{bmatrix} (b=d=0)$$ and $$\begin{bmatrix}i\frac1{\sqrt2} \\ i\frac1{\sqrt2}\...
Mariia Mykhailova's user avatar
3 votes

Encoding circuit for $[\![6, 4, 2]\!]$ code

We can obtain an encoding circuit for the $[\![m,m-2,2]\!]$ code for any even $m$ by generalizing the circuit displayed in the question. More precisely, for every new qubit we prepend a CNOT gate with ...
Adam Zalcman's user avatar
  • 22.5k
3 votes
Accepted

Encoding circuit for $[\![6, 4, 2]\!]$ code

This can easily be done using stac. More explanations of the process for generating the encoding circuit is explained in a previous answer. But, since, this question is specifically asking for $[[2m, ...
Abdullah Khalid's user avatar
3 votes

How to simulate a $CNOT$ only using a single qubit?

Quantum operations have to be reversible and the operation you described is not reversible. Both 0 and 1 map to 0, so it is a many-to-one function and thus if you are just given 0 you have no ...
amihart's user avatar
  • 41
3 votes

How to apply rotation about X and Z in stim?

See Gates supported by Stim in stim's doc/ directory. Stim only supports stabilizer gates, so it can't rotate by 2 radians around the Z axis like you are doing in your circuit. The closest would be ...
Craig Gidney's user avatar
  • 37.1k
3 votes
Accepted

How to interpret the circuit that measures stabilizers in the 5-qubit error correcting code

The circuit image from wikipedia is quite mangled, and I am not quite sure if correct. Here is a nicely laid out syndrome measurement circuit for the $[[5,1,3]]$ code. Here, the top five qubits are ...
Abdullah Khalid's user avatar
3 votes

How to implement the modular exponentiation implementation in Shor's algorithm?

$a^{-1}$ is an integer, because you're working in modular arithmetic. $a^{-1}$ is the value that satisfies $a \cdot a^{-1} = 1$. For example, on a clock, 5-oclock times 5-oclock equals 25-oclock which ...
Craig Gidney's user avatar
  • 37.1k
3 votes

How to implement the modular exponentiation implementation in Shor's algorithm?

Given two coprime integers $a$ and $N$, you can compute $a^{-1} \text{ mod } N$ efficiently classically by using the extended Euclidean algorithm even if the factorization of $N$ is unknown. This is ...
Martin Ekerå's user avatar

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