Quantum computation and computational issues related to quantum mechanics

learn more… | top users | synonyms (1)

1
vote
0answers
71 views

Proof that BQP is contained in this classical complexity class

I am trying to show that BQP is contained in the the complexity class class of decision problems for which there exists a classical algorithm that, for problem size n, solves the problem using an ...
6
votes
2answers
257 views

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

DISCLAIMERI do apologize in advance if this question turns out to be silly, for some trivial reason that I may be overlooking in this moment. Suppose for a moment that $\mathbf{P} = ...
0
votes
0answers
58 views

Understanding efficient classical simulation of quantum computing

I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate ...
1
vote
0answers
21 views

Coset state of $3$-node graph isomorphism problem

The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...
2
votes
0answers
76 views

Complexity: simulated annealing vs. quantum annealing

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms? In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
0
votes
2answers
160 views

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974). I am wondering if it is also known whether ...
6
votes
0answers
110 views

Problems in BQP but conjectured to be outside P

Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain ...
-5
votes
1answer
122 views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
1
vote
1answer
90 views

Continued Fraction Algorithm in Shor's Algorithm

I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$. We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies ...
0
votes
0answers
76 views

Which n-qubit Hamiltonians are measurable in poly-time?

Which n-qubit Hamiltonians (or, equivalently Hermitian operators) can feasibly be measured in polynomial time? (as opposed to simulated in poly-time) What the relationship to the complexity of the ...
2
votes
0answers
69 views

Proofs to verify quantum states without revealing their description

Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$ where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state. Assume the function is a one-to-one ...
0
votes
0answers
23 views

Hardness of finding similar (quantum) states

Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce ...
3
votes
1answer
70 views

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned? Given an unknown state ${\rvert \psi ...
3
votes
1answer
73 views

Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of ...
4
votes
1answer
124 views

Probabilistic and quantum analog of $FP$ and $FNP$?

Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?
24
votes
4answers
2k views

If P = NP were true, would quantum computers be useful?

Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on ...
3
votes
1answer
145 views

Efficient generation of permutational invariant quantum states

Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one: $$ |\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} ...
0
votes
1answer
90 views

How does one extend local checkability to quantum complexity classes?

How does one extend local checkability to quantum complexity classes like BQP? Or are quantum algortihms inherently holistic?
9
votes
1answer
329 views

Quantum algorithms for QED computations related to the fine structure constants

My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like ...
3
votes
1answer
146 views

The relationship between QCMA and QMA in the Turing and Communication model

First my background about computational complexity is still beginner. Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial ...
11
votes
1answer
119 views

Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

I am considering ideas about exact quantum algorithms. In particular, I am considering likely limitations of $\mathsf{EQP}$, which consists of languages exactly decideable by polytime-uniform quantum ...
0
votes
1answer
59 views

Why are sub-normalized states studied in quantum computation?

By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In generalised fidelity etc). I'd be ...
3
votes
1answer
149 views

Why is shifting bits different from shifting qubits?

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a ...
1
vote
1answer
154 views

What is the Quantum Cheshire Cat experiments' import to Quantum Computing?

What is the significance of the Quantum Cheshire Cat to Quantum Computing? To recap, the Quantum Cheshire Cat experiment proved it was possible to separate a neutrons' spin from the neutron. Or, in ...
3
votes
1answer
80 views

Complexity class for quantum computer with commutative gates

BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In quantum computer allowed operations can be ...
49
votes
2answers
4k views

Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
4
votes
4answers
812 views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
0
votes
0answers
103 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
7
votes
3answers
946 views

Are there any cases where quantum has given insight for classical algorithms?

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum ...
5
votes
1answer
88 views

Is any QMA-intermediate problem known?

Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been ...
0
votes
0answers
49 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
5
votes
1answer
342 views

Applications of HHL's algorithm for solving linear equations

In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge ...
23
votes
1answer
388 views

The randomized query complexity of the conjoined trees problem

An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
7
votes
0answers
50 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
11
votes
2answers
394 views

Quantum algorithms based on transforms other than Fourier transforms

In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier ...
13
votes
1answer
266 views

Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory. Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of ...
1
vote
0answers
41 views

Non-Transversal Fault Tolerant Gate

I have always heard that transversality is a sufficient, not a necessary condition for fault-tolerance in quantum computation. However, I have never seen any examples of non-transversal fault tolerant ...
13
votes
6answers
2k views

Is there a formal proof that quantum computing is or will be faster than classical computing?

Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?
0
votes
1answer
145 views

Quantum Fourier Transform question regarding measurement

When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first ...
8
votes
0answers
103 views

Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?

The standard proof that BQPSPACE is in PSPACE relies on a Savitch game type analysis on path integrals. However, it assumes the time running length for BQPSPACE is at most exponentially long. This is ...
2
votes
0answers
46 views

How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?

I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says, Since ...
2
votes
1answer
1k views

A quantum algorithm for GCD

Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in ...
4
votes
1answer
135 views

Hardness of quantum circuit equivalence?

Given two poly-sized quantum circuits $C_1$ and $C_2$ on $n$ qubits with a universal gate set generated by some finite set of one and two qubit gates. I'm thinking of the gates $\langle H, T, ...
6
votes
1answer
205 views

What complexity issues are there in considering quantum algorithms with infinite gate-sets?

Short Version Suppose that you want to consider a model of quantum computation in which the gates used in the circuits may depend on the input size. Are there pitfalls to avoid when defining the ...
4
votes
2answers
287 views

Are two-qubit unitaries necessary for universal quantum computation?

I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said, Two-qubit ...
4
votes
0answers
121 views

Generating quadratic optimization problems amenable to quantum annealing

Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a ...
9
votes
0answers
266 views

How powerful is exact “quantum” computing if you suspend unitarity?

Short Question. What is the computational power of "quantum" circuits, if we allow non-unitary (but still invertible) gates, and require the output to give the correct answer with certainty? This ...
4
votes
1answer
338 views

Applications of Quantum Walks?

Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks? I have researched a fair amount on how quantum walks operate and their ...
5
votes
1answer
185 views

Grover's search algorithm for 3 coloring

According to Arora & Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in ...
1
vote
1answer
240 views

Running Simon's algorithm on D-wave machine

I was wondering whether Simon's algorithm could be run on a D-wave machine. The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained ...