Most Popular
1500 questions
10
votes
1 answer
What are examples of non-oracular versions of famous oracular problems?
Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently constructible.
Recently, Bravyi et al proposed a…
BlackHat18
- 1,313
- 8
- 16
10
votes
1 answer
How is CNOT gate physically implemented in IBM Q?
This is because if control qubit is in arbitrary state then how can it be made to control the CNOT gate? What is the interface between Control Qubit and CNOT Gate?
Ashish
- 285
- 2
- 9
10
votes
2 answers
Definition of the Pauli group and the Clifford group
There seem to be two definitions of the Pauli group. In Nielsen and Chuang, the Pauli group on 1 qubit is defined as
\begin{align*}
\mathcal{P}_1 = \{\pm I, \pm iI, \pm X, \pm iX, \pm Y, \pm iY, \pm Z, \pm iZ\} = \langle X, Y,…
snsunx
- 303
- 2
- 7
10
votes
0 answers
Anti-symmetrization on the lattice
Assume, I'm using a system of qubits to simulate a fermionic system.
If I'm using the second-quantized formalism (e.g. orbitals in quantum chemistry), the anti-symmetric nature of the fermionic wave functions can be taken into account by means of…
mavzolej
- 1,921
- 7
- 17
10
votes
1 answer
What are the basics needed to learn quantum computing?
I was very inspired by Michio Kaku's explanation on the possibilities of quantum computing and also listening to Talia Gershon's talk on it.
As I come from a business & analytics background, what materials can I begin exploring to prepare to learn…
jchua
- 203
- 1
- 8
10
votes
3 answers
What precisely is the quantum extended Church-Turing thesis?
Context
Prof. Aaronson mentions that the quantum extended Church-Turing (quantum ECT) thesis has no known counterexamples cf. around 14:18 but doesn't mention its precise statement.
Questions
What precisely is the statement of the quantum extended…
Sanchayan Dutta
- 17,497
- 7
- 48
- 110
10
votes
2 answers
How is it possible to implement unitary operator when its size is exponential in inputs?
A quantum circuit can use any unitary operator. Its matrix is exponential in the number of input bits. In practice how can this ever be possible (aside from operators which are tensor products), i.e. how can you construct exponential size matrix?
John77
- 101
- 3
10
votes
3 answers
What is the "Stinespring Dilation"?
I've consulted Nielsen and Chuang to understand the Stinespring Dilation, but wasn't able to find anything useful. How does this operation relate to partial trace, Kraus operators, and purification?
Jimit Bavishi
- 109
- 1
- 4
10
votes
2 answers
Show that these two expressions for the oracle transformation are equivalent
Suppose $x \in \{0,1\}^n$. The standard way to make a query is with an oracle $O_x$ that given an input $|i,b \rangle $ returns $|i,b \oplus x_i \rangle$. Via the phase kick-back trick, this can be used to make another type of query $O_{x}^{''}$…
Karl
- 359
- 1
- 10
10
votes
3 answers
Does Shor's algorithm end the search for factoring algorithms in the quantum world of computation?
In other words, will factoring research remain solely in the classical world or are there interesting research on-going in the quantum world related to factoring?
R. Chopin
- 1,199
- 6
- 17
10
votes
2 answers
Why is quantum Fourier transform required in Shor's algorithm?
I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem or period of modular exponentiation sequence of…
Poramet Pathumsoot
- 327
- 2
- 7
10
votes
2 answers
Who discovered the phase kickback trick?
Was it David Deutsch? Can you say who was the first paper to mention the phase kickback trick?
R. Chopin
- 1,199
- 6
- 17
10
votes
4 answers
Is there any company that backs and implements diamond vacancy quantum computers?
It is known that there are big companies behind the specific qubit implementations (e.g. ion traps, superconducting loops, topological qubits, etc.). But I have not managed to find the company that is backing/implementing diamond vacancy quantum…
TomR
- 413
- 2
- 7
10
votes
1 answer
What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?
Context:
I was going through John Watrous' lecture Quantum Complexity Theory (Part 1) - CSSQI 2012. Around 48 minutes into the lecture, he presents the following:
No relationship is known between $\mathsf{BQP}$ and $\mathsf{NP}$...they are…
Sanchayan Dutta
- 17,497
- 7
- 48
- 110
10
votes
1 answer
Can I remove gates from a QuantumCircuit?
Suppose I want to implement run several circuits one after another, but they are constructed in a similar fashion. I could reinstantiate a QuantumCircuit for each iteration, like this:
params = np.linspace(0, 2 * np.pi, num=20)
for p in params:
…
Alexey Uvarov
- 684
- 5
- 14