Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

12
votes
1answer
369 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 ...
10
votes
0answers
244 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 = ...
8
votes
2answers
188 views

Largest set allowing one-step unstructured quantum search

What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle? The question is interesting since Grover'...
-3
votes
1answer
161 views

Lower bounds on $Q_{\epsilon}(IP)$

I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product. I have Nayak's lower bound, but I am not sure ...
5
votes
1answer
170 views

Communicating a string of zeros and ones quantumly

Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and transmits a ...
11
votes
1answer
426 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 ...
5
votes
1answer
132 views

Known properties of a specific class of quantum states

Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as $|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n (-1)^{x_i}|i\rangle$,...
7
votes
1answer
202 views

A promise problem to decide whether two given pure quantum states are close or far apart

Consider this problem in quantum cryptography: We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which $$\left|\...
-1
votes
2answers
280 views

Will we be able to use the current software in quantum computers? [closed]

I'm not sure if this should go here, so my apologies. The fact is that lately I have heard a lot about quantum computers and that they are not that far away. As it is a totally new technology, which ...
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 ...
17
votes
1answer
325 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 ...
7
votes
1answer
377 views

Layman Interpretation: Quantum Factoring Algorithm

I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media. So, I'm hoping that somebody will be able to help me ...
3
votes
0answers
109 views

Polynomial Quantum Algorithm for Graph Isomorphism? [duplicate]

Possible Duplicate: NP-intermediate problems with efficient quantum solutions Many suspect that quantum computers will not be able to efficiently solve NP-complete problems and thus focus on the ...
11
votes
2answers
453 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 $...
17
votes
1answer
321 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{...
13
votes
0answers
299 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 ...
8
votes
3answers
766 views

1-way Quantum Finite Automata Example Question

I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful)....
4
votes
1answer
243 views

Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm? Are known any (classical) approximation algorithms ...
10
votes
1answer
380 views

Uniform way of quantifying “branching” in nondeterministic, probabilistic, and quantum computation?

The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is ...
5
votes
1answer
438 views

Quantum algorithms for determining whether two sets intersect

Grover's algorithm is a quantum algorithm that is able to locate a special record in an $N$ element unsorted database in $\Theta(\sqrt{N})$ time. What quantum algorithms are known to determine whether ...
10
votes
1answer
556 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". ...
6
votes
1answer
356 views

Quantum capacity for ensemble of Pauli channels

In Preskill's quantum computing notes Chapter 7 approximate page 82, he shows that a Pauli channel has capacity $Q \geq 1-H(p_I,p_X,p_Y,p_Z)$ where $H$ is Shannon entropy and $p_I, p_X, p_Y, p_Z$ are ...
26
votes
0answers
422 views

Adiabatic quantum computing with level crossings

Question. In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
24
votes
2answers
299 views

Computational complexity of quantum optics

In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table: MY question is three-fold: ...
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 ...
1
vote
0answers
143 views

Is there a lower bound for the decisional Grover search problem?

What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ ...
11
votes
1answer
91 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 ...
15
votes
5answers
407 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?
4
votes
0answers
184 views

Do the quantum communication complexity lower bounds hold when parties can send a “duplicated” qubits?

This question continues from the previous question where I mistakenly asked a question that is too general. In quantum communication complexity, we always assume that Alice and Bob have unlimited ...
0
votes
2answers
336 views

Are Alice and Bob allowed to copy qubits in quantum communication complexity model?

In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity. What ...
23
votes
5answers
619 views

Universal sets of gates for SU(3)?

In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an ...
76
votes
7answers
41k views

What would a very simple quantum program look like?

In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first ...
15
votes
0answers
60 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 ...
10
votes
1answer
233 views

Lower bounds for quantum circuits using the geodesic framework

Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance ...
14
votes
5answers
531 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 ...
17
votes
3answers
332 views

Models of computation strictly between classical and quantum in terms of query complexity

It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity. Are there other models (natural or artificial) that are strictly ...
0
votes
0answers
383 views

Is it possible to add quantum physics theory to traditional machine learning algorithms to get more accurate results

Lets suppose your data set includes locations in several dimensions and the kind of entity which is the class of the data set, is there other kind of information you need to add (such as times, ...
18
votes
2answers
175 views

Temporally Flat One-Way Quantum Computing

I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum ...
6
votes
1answer
709 views

Analytic solutions in semidefinite programming (SDP)

From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
24
votes
2answers
94 views

What is the best lower bound for the fault-tolerance threshold in quantum computing?

It is well established that there exists a noise threshold for quantum computation, such that below this threshold, the computation can be encoded in such a way that it yields the correct result with ...
4
votes
1answer
347 views

Quantum cellular automata

This questions is cross-posted from MathOverflow A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use ...
10
votes
2answers
363 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 ...
50
votes
3answers
1k views

Rigorous security proof for Wiesner's quantum money?

In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank ...
27
votes
5answers
847 views

Quantum proofs of classical theorems

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be ...
26
votes
4answers
1k views

Quantum approximation algorithms

It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation ...
9
votes
0answers
112 views

Non-tomographical certification of projectors, using product states?

I'm interested in operational ways of demonstrating (with high probability of confidence, in an error-free setting) that a POVM operator on n-qubit states is a projector. Specifically, I'm interested ...
7
votes
0answers
193 views

Are the minimal quantum and classical span programs the same?

A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity. A span program for a function $f: \{0,1\}^n \...
14
votes
1answer
660 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 ...
-6
votes
1answer
341 views

Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?
7
votes
3answers
3k views

Ed. Witten's new paper and the simulation of a quantum field theory

Context: Ed. Witten recently wrote a potentially revolutionary paper where he showed that under certain conditions, a Chern-Simons path integral in three dimensions is equivalent to an N = 4 path ...