New answers tagged

3 votes
Accepted

Complexity of controlled-$U^j$ operations in QPE applied to Hamiltonian simulation

Your understanding is almost there. If $k$ is the number of desired bits, then yes its exponential in $k$. However, given $k$ correct bits of the eigenvalue, the error is $1/2^{k+1}$. This is because ...
xzkxyz's user avatar
  • 451
2 votes
Accepted

Non-linear quantum mechanics and NP-complete problems

Be careful - the P vs. NP problem (or even the BQP vs. NP problem) is a mathematical problem about platonic Turing machines, detached from this real world. The Abrams and Lloyd paper is an interesting ...
Mark Spinelli's user avatar
0 votes

Complexity of Variational Quantum Eigensolvers

The decomposition of a Hamiltonian into Pauli strings is not always efficient. The general problem of decomposing a Hamiltonian expressed in an arbitrary basis into Pauli operators can be ...
Bram's user avatar
  • 564
1 vote

Prove that there is no polynomial size quantum algorithm for a Simon's problem with no promise on the input

Consider the set of values taken by $f$; that is, consider the range of $f$. For any arbitrary function $f$, this range can be partitioned as follows: There could be a first set of images $A$ that ...
Mark Spinelli's user avatar
3 votes
Accepted

What is an example of a problem that we strongly suspect lies in NP $\cap$ co-NP but not in BQP?

Regarding the second question as to whether there's a problem splitting NP$\cap$coNP from BQP, assuming (as is standard) that coAM=coNP, then Graph Isomorphism may be such a candidate. In particular, ...
Mark Spinelli's user avatar
-1 votes

Prove that there is no polynomial size quantum algorithm for a Simon's problem with no promise on the input

Assume You have a function $f(x) := \begin{cases} 1 & \text{if } x = \widehat{x} \\ 0 & \text{else}\end{cases} $ for an arbitrary value $\widehat{x}$....
Sezzart's user avatar
  • 160
2 votes
Accepted

The time complexity of quantum circuit

There are several ways how to compute complexity of a quantum circuit. Number of gates to be executed and how this number is dependent on number of qubits is definitely good starting point. Once ...
Martin Vesely's user avatar
0 votes

Classical electronics controls from both sides - could we do it for some quantum electronics?

So here is your Question: Could more symmetric quantum computers be built by implementing time/CPT symmetry through two-way control similar to classical electronics' push and pull of electrons? Answer:...
Zero's user avatar
  • 59
4 votes

What is the oracle in every quantum algorithm?

There are a couple of different bits of the philosophy of how we use oracles that we need to touch on here: when we use an oracle, it's often trying to make some claims about how fast the algorithm ...
DaftWullie's user avatar
  • 58.1k
0 votes

Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?

I won't name an explicit example of an algorithm. But I will add a reason why a search for a QFT-less Quantum algorithm with superpolynomial speedup (w.r.t classical) might be extremely challenging. (...
Manish Kumar's user avatar
4 votes
Accepted

What is stopping FACTORING from being BQP-complete?

At a rigorous level, nothing is necessarily stopping any of these things, because no one can even prove that P≠PSPACE. If P=PSPACE, then every problem in P is BQP-complete as well as NP-complete, ...
Greg Kuperberg's user avatar
6 votes
Accepted

Requirement of vector 'b' in the definition of Phase Estimation Sampling (PES)

The discussion in question appears to be discussing usage of the Quantum Phase Estimation algorithm when we do not have access to an eigenstate $|\eta_j \rangle$ of the unitary matrix $U$ in question. ...
jsbaker's user avatar
  • 156
2 votes
Accepted

How many gates are necessary to implement an arbitrary n-qubit permutation unitary?

Using the idea of parameter counting, suggested by @NorbertSchuch, I was able to find more information on that topic and work out a proof that the number of required gates is indeed exponential. The ...
QNA's user avatar
  • 171

Top 50 recent answers are included