# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

337 questions
Filter by
Sorted by
Tagged with
90 views

### Period of a Multivariable Function using Quantum Computing

consider a function $$f(x_1,x_2...x_n)$$ I am told it is possible to compute the period of the function as a vector $$<l_1,l_2...l_n>$$ where each l denotes the period of the function for ...
173 views

### Relationship between size of quantum superposition and rate of decoherence

I am new here in StackExchange and this will be my first question to ask. I have a background in Computer Science and I am interested in looking into Distributed Quantum Computing (DQC). I have read ...
144 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$ ...
256 views

### Separating the QIP hierarchy

Background: I'm a CS grad student. I've taken a course on computational complexity. Question: Can you suggest an introductory book on quantum computation, especially regarding the details of ...
304 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 ...
338 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 ...
262 views

### Finding all solutions by Grover search(not superposition)

When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this: 1) Do Grover search, get ...
68 views

### Grover's algorithm, M out of N, when M is large

The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries. I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to ...
86 views

### Question about discarding the second register in the standard approach of hidden subgroup algorithm

My questions: What does discarding the second register mean for the standard approach of hidden subgroup algorithm? Why does discarding let the first register end up in a mixed state? My ...
91 views

### Confusion with the proof of constraints for a particular adiabatic quantum evolution

[This might be related to one of my previous unanswered questions.] This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
97 views

### How are new probabilities computed when simulating measurement on a set of qubits?

Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure: |000> -> a |001> -> b |010> -> c |011> -> d |100> -> e |101> -> f |...
273 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 ...
135 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?
40 views

### Hidden subgroup problems in a tower of subgroups

Let $H$ be a hidden subgroup of $G_1$ that is indistinguishable from subgroup $H^{\prime}$ by quantum Fourier sampling. Now take a larger group $G_2$ such that it contains $G_1$. Now if I do quantum ...
149 views

### Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
97 views

### What is the relationship between quantum tomography and quantum error correction?

To realize correct quantum computing it seems that both quantum error correction and quantum tomography would be necessary. Is this true? What is the relationship between these two fields?
30 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 ...
124 views

### Determining if a function is constant or not using period finding

Consider an arbitrary boolean function $$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as: $$f(x_1, x_2 ... x_n)$$ where each $x_i$ is a boolean variable We note ...
126 views

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 ...
252 views

### How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?

Suppose that I have a normalized quantum state $\sum_n a_n |n\rangle$, is there a quantum operation/circuit so that I can get $\frac{1}{N} \sum_n e^{i a_n} |n\rangle$ at output? How?
1k views

### Addition on a quantum computer

From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers. For a simple arithmetic operation such as a+b+c+d where ...
99 views

### Can the aliens hustle us with Chaitin's constant?

Premise Suppose you are an alien and want to fool Earthlings you have extracted the value of Chaitin's Constant. Does the strategy below work? If so, any explicit(/basic ideas for) algorithm? If not, ...
144 views

### Complexity class on quantum computation and classic ones

Does the complexity speedup in superpolynomial by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in ...
136 views

### Dimension of the Fourier transform for $S_5$ [closed]

My question: What is the dimension of the Fourier transform for $S_5$? My effort: The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
395 views

...
183 views

### The factoring problem reduces to order finding or is it the other way around? [closed]

initially i was not at all equipped in theoretical computer science and knew only basics of number of theory. I started working from scratch on the age old problem of primality testing which led me to ...
163 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 ...
127 views

### Can a computer generated organism be self aware? [closed]

Imagine that a computer generating a small universe similar to our own. Same table of elements, same physics, ect. Starting from the very beginning, with the creation of all the atoms in the ...
206 views

### Is the sub-bit model of quantum computation equivalent to other models? [closed]

In a comment to this question Peter Shor asked me for a reference about the third described in the question point of view, namely, that quantum computers can be described as computers that can ...
349 views

### Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?