Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
17
votes
3answers
755 views

Are there any known implementations for quantum computing constructs?

Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...
17
votes
5answers
3k views

Real world applications of quantum computing (except for security)

Let's assume that we have built an universal quantum computer. Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it? I am ...
17
votes
2answers
396 views

Is PARITY in QAC_0 (if that even makes sense)

As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in fact const-dept circuits require EXP number of gates. What about QUANTUM circuits? a) Can PARITY be done with a ...
17
votes
1answer
1k views

The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and ...
17
votes
1answer
360 views

Geometric picture behind quantum expanders

(also asked here, no replies) A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{...
17
votes
1answer
350 views

Which results make quantum space interesting?

Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation? I know many interesting results for quantum computation with sublogarithmic space bounds ...
17
votes
1answer
483 views

Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that ...
17
votes
0answers
484 views

Quantum Hardness of Finding Nash Equilibria

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen. Their main result is that the existence of ...
16
votes
1answer
804 views

Reading up on $BQP = BPP^{BQNC}$

What should I read to understand this problem? The power of small-depth quantum circuits. Is $BQP = BPP^{BQNC}$? In other words, can the "quantum" part of any quantum algorithm be compressed ...
16
votes
1answer
419 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 any ...
15
votes
6answers
7k views

Quantum computing project ideas

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?
15
votes
5answers
571 views

What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?

The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies ...
15
votes
5answers
565 views

Software package for decomposing quantum circuits

Is there any software package allowing decomposition of unitaries from $U(2^n)$ into quantum circuits over a predefined universal gate set?
15
votes
2answers
961 views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
15
votes
6answers
3k 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?
15
votes
2answers
700 views

Quantum PAC learning

Background Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If ...
15
votes
1answer
655 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 ...
15
votes
0answers
73 views

Lower bounds for quantum circuits using the geodesic framework

(this question is a crosspost from cstheory. I've incorporated the one answer there into the question) Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum ...
14
votes
1answer
763 views

Is there a quantum NC algorithm for computing GCD?

From the comments on one of my questions on MathOverflow I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
14
votes
2answers
1k views

Best method of Error Correction in Quantum Key Distribution

As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared ...
14
votes
1answer
749 views

What is known about multi-prover interactive proofs with short messages?

Beigi, Shor and Watrous have a very nice paper on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is ...
13
votes
3answers
495 views

One-way quantum verification

The theory of cluster-state computation is well-established by now, showing that any BQP circuit can be modified so it uses only single qubit quantum gates, possibly classically controlled, provided ...
13
votes
2answers
619 views

One-shot quantum hitting times

In the paper Quantum Random Walks Hit Exponentially Faster (arXiv:quant-ph/0205083) Kempe gives a notion of hitting time for quantum walks (in the hypercube) that is not very popular in the quantum ...
13
votes
1answer
332 views

Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

Context. I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I ...
13
votes
0answers
301 views

Is there any known nontrivial result on QIP systems having a space-bounded verifier?

Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier? The only paper I know is An application of quantum finite automata to interactive ...
12
votes
2answers
637 views

What is the Relationship between QMA and AM?

I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$. I was surprised about this ...
12
votes
1answer
5k views

Clifford group quantum operations and classical computation

The Clifford group of quantum operators is generated by the quantum operations: Controlled-Z, Hadamard, and Phase ($= |0\rangle\langle0| + i |1\rangle\langle1|$). A circuit composed only of these ...
12
votes
5answers
2k views

List of quantum-inspired algorithms

Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra: A quantum-inspired classical ...
12
votes
1answer
346 views

Transitioning from quantum to classical random walks on the line

Quick version Are there models of decoherence for the quantum walk on the line such that we can tune the walk to spread as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$? Motivation Classical random ...
12
votes
1answer
219 views

Is there a survey of the field of quantum automata?

I'm looking for a survey paper of the important concepts in the field of Quantum Automata. I've found Quantum Automata Theory -- A Review by Hirvensalo, but it sounds too succinct to grasp the topic. ...
12
votes
1answer
400 views

Can quantum algorithms with exponential speed-up be rederived using span-programs?

The general adversary lower-bound is now known to characterize quantum query complexity due to breakthrough work by Reichardt et al. The same line of work also establishes connections to the span ...
12
votes
1answer
304 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 ...
11
votes
2answers
2k views

Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

I believe the answer to this question is well-known; but, unfortunately, I don't know. In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the ...
11
votes
7answers
1k views

Quantum Computation - Postulates of QM

I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book. I wanted to ask if anyone could try finding time to help me with whats going on with the ...
11
votes
2answers
537 views

Nonlocal Games and Quantum Communication

I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at ...
11
votes
1answer
421 views

What does a tangible Quantum-Gate look like?

I'v read published books, articles and papers about Quantum-Computing. I found that all the materials I've seen are, instead of describing quantum gate from basic physics to abstraction, trying hard ...
11
votes
1answer
601 views

What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

JBV suggested I turn some comments into a question, so here goes. Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". ...
11
votes
1answer
468 views

Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$? This problem can be ...
11
votes
2answers
817 views

Problems with no known quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
11
votes
1answer
161 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 ...
11
votes
2answers
313 views

Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem

I've difficulty in understanding the last steps of the AHSP algorithm. Let $G$ be an abelian group and $f$ be the function which hides the subgroup $H$. Let $G^*$ represent the dual group of $G$. ...
11
votes
1answer
115 views

Decidability/algorithm for checking universality of a quantum gate set

Given a finite set of quantum gates $\mathcal{G} = \{G_1, \dots, G_n\}$, is it decidable (in computation theoretic sense) whether $\mathcal{G}$ is a universal gate set? On one hand, "almost all" gate ...
11
votes
2answers
522 views

Notation for a Conditional Hamiltonian Evolution Operator

I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write Next we apply the conditional Hamiltonian evolution $...
11
votes
1answer
472 views

Why must QMA complete problems be promise problems?

I'm reading Watrous's excellent survey paper on paper on quantum complexity theory. In it he states that it would be surprising if a QMA -complete problem were found to have a vacuous promise (I.e. Be ...
11
votes
0answers
255 views

What are the most recent developments in small-depth quantum circuits?

Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge: The power of small-depth quantum circuits. Is $BQP = ...
10
votes
2answers
429 views

Restricting entries of unitary operators to real numbers and universal gate sets

In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-...
10
votes
4answers
480 views

Quantum Bell-Type Inequalities

I'm curious if someone could recommend some supplementary material for gaining a deeper understanding of the paper : "Some Results and Problems on Quantum Bell-Type Inequalities - Tsirelson". ...
10
votes
4answers
674 views

Bounding the gap between quantum and deterministic query complexity

Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, ...
10
votes
2answers
382 views

Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

Deutsch's algorithm is a well known quantum computing $f(0) + f(1)\mod{2}$ with only one one evaluation of $f$. If we replace $+$ with $\cdot$ the problem seems to become rather different. My ...
10
votes
1answer
614 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 ...

1
2
3 4 5
8