Most Popular
1500 questions
13
votes
1 answer
How does Fourier sampling actually work (and solve the parity problem)?
I'm writing with respect to part I and part II of the Fourier sampling video lectures by Professor Umesh Vazirani.
In part I they start with:
In the Hadamard Transform:
$$|0...0\rangle \to \sum_{\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle$$
$$|u\rangle…
Sanchayan Dutta
- 17,497
- 7
- 48
- 110
13
votes
2 answers
Good introductory material on quantum computational complexity classes
I wish to learn more about computational complexity classes in the context of quantum computing.
The medium is not so important; it could be a book, online lecture notes or the like. What matters the most are the contents.
The material should…
Kiro
- 1,975
- 16
- 24
13
votes
0 answers
Does the Curry-Howard correspondence have a quantum-specific type system?
In Wikipedia we can read that
the Curry–Howard correspondence is a correspondence between formal proof calculi and type systems for models of computation. In particular, it splits into two correspondences. One at the level of formulas and types…
fr_andres
- 754
- 7
- 16
13
votes
3 answers
Superposition of quantum circuits
Given a quantum circuit $C_1$ that generates a state $\vert\psi\rangle$ and another circuit $C_2$ that generates $\vert\phi\rangle$, is there a way to construct a circuit that outputs
$$\frac{1}{\sqrt{2}}(\vert \psi\rangle +\vert\phi\rangle)$$
using…
Kolp
- 133
- 3
13
votes
5 answers
Why do error correction protocols only work when the error rates are already significantly low to begin with?
Quantum error correction is a fundamental aspect of quantum computation, without which large-scale quantum computations are practically unfeasible.
One aspect of fault-tolerant quantum computing that is often mentioned is that each error-correction…
glS
- 24,708
- 5
- 34
- 108
13
votes
1 answer
What is the probability $\Pr(\|U-I\|_{\rm op}<\varepsilon)$ of a Haar-random unitary being close to the identity?
If one generates an $n\times n$ Haar random unitary $U$, then clearly $\Pr(U=I)=0$. However, for every $\epsilon>0$, the probability
$$\Pr(\|U-I\|_{\rm op}<\varepsilon)$$
should be positive.
How can this quantity be computed?
Calvin Liu
- 183
- 4
13
votes
4 answers
Who built the first quantum computer using at least two qubits?
In my previous question I asked who invented a quantum computer using qubits.
As a follow-up to this question I want to ask who built the first quantum computer using at least two qubits.
During my research I have discovered that in 1998, Jonathan…
luap42
- 1,047
- 1
- 14
- 28
13
votes
1 answer
What is the leading edge technology for creating a quantum computer with the fewest errors?
Which technological path seems most promising to produce a quantum processor with a greater quantum volume (preferring fewer errors per qubit over more qubits), than Majorana fermions?
The preferred format for the answer would be similar to:
"Group…
Rob
- 2,307
- 1
- 14
- 30
13
votes
3 answers
Why does a Hamiltonian have to be Hermitian?
Starting from:
$$
-i\hbar \frac{d|\psi⟩}{dt} = H|\psi⟩
$$
I was able to do some working to prove that $U$ in the corresponding discrete representation
$$
U(t_1,t_2) = exp\frac{-iH(t_2-t_1)}{\hbar}
$$
is unitary if and only if $H$ is Hermitian. That…
Alexander Soare
- 636
- 4
- 16
12
votes
3 answers
Does the quantum Fourier transform have many applications beyond period finding?
(This is a somewhat soft question.)
The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster.
The QFT is famously at the core of Shor's algorithm for period finding. It also comes up in a few…
tparker
- 2,711
- 11
- 26
12
votes
0 answers
Status of hidden shift and hidden subgroup problems
We know that solving a hidden subgroup problem over a non-commutative group is a long standing problem in quantum computing even for groups like $D_{2n}$ (alternatively can be written as $\mathbb{Z}_n \rtimes \mathbb{Z}_2$) for general $n$. What…
Root
- 479
- 2
- 11
12
votes
1 answer
Quantum algorithms for Prolog or automated theorem proving?
Are there quantum algorithms for Prolog (SLD resolution - unification and depth-first-search) or for automated theorem proving in general (negation, resolution, and SAT)?
Usually automated theorem proving involves SAT problem for the negation of…
TomR
- 413
- 2
- 7
12
votes
2 answers
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set
I was recently going through the paper titled "Quantum supremacy using a programmable superconducting processor" by NASA Ames Research Centre and the Google Quantum AI team (note that the paper was originally posted on the NASA NTRS but later…
Sanchayan Dutta
- 17,497
- 7
- 48
- 110
12
votes
3 answers
Big Endian vs. Little Endian in Qiskit
I've noticed that Q# favors Little Endian. Meaning that most operations are designed for this type of encoding.
Is is it the same with Qiskit?
Sorin Bolos
- 611
- 5
- 11
12
votes
2 answers
How to create quantum circuits from scratch
I am doing self-study at the moment using primarily the book: Quantum Computing a Gentle Introduction by Eleanor Rieffel and Wolfgang Polak.
Getting through the earlier chapters and exercises went quite well (fortunately the earlier chapters had…
Joery
- 173
- 8