Most Popular
1500 questions
10
votes
1 answer
How to reduce circuit elements of a decomposed $C^2(U)$ operation?
This question refers to Nielsen and Chuang's Exercise 4.22:
Prove that a $C^2(U)$ gate (for any single-qubit unitary U) can be
constructed using at most eight one-qubit gates, and six controlled-not gates.
To prove this, I decomposed all $C(V)$…
Eesh Starryn
- 401
- 5
- 12
10
votes
0 answers
Strong vs weak simulations and the polynomial hierarchy collapse
(Edited to make the argument and the question more precise)
An argument for quantum computational "supremacy" (specifically in Bremner et al. and the Google paper) assumes that there exists a classical sampler that outputs a probability $q_x$, $x…
Ninnat Dangniam
- 201
- 1
- 4
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,527
- 9
- 22
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
- 295
- 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
4 answers
What does fidelity mean?
I am learning qiskit software and this term keeps popping up and I am unable to get a grasp on the technical definition given by wikipedia. For example, the functions state fidelity and process fidelity.
Eesh Starryn
- 401
- 5
- 12
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
- 2
- 8
10
votes
2 answers
Will quantum computers be able to solve the game of chess?
Will it be possible to use quantum computing to one day solve the game of chess? If so, any estimate as to how many qubits it would require?
The game of checkers has already been solved through back in 2007 after years of number crunching. But they…
lkessler
- 201
- 3
- 6
10
votes
2 answers
How to prove that the query oracle is unitary?
The query oracle: $O_{x}|i\rangle|b\rangle = |i\rangle|b \oplus x_{i}\rangle$ used in algorithms like Deutsch Jozsa is unitary. How do I prove it is unitary?
Divyat
- 103
- 5
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
- 11
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,219
- 8
- 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
- 8
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,219
- 8
- 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
- 423
- 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,945
- 8
- 50
- 112