# Tag Info

23

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: (¬x1 ∨ ¬x3 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4) ∧ (x1 ∨ ¬x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧ (¬x1 ∨ x2 ∨ ¬x3) Or, in table form with each row being a 3-clause, x meaning "this variable false", o ...

21

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time. There are a number of ways to do this. To name just two: D: given n and k, does n have a divisor d satisfying 1 < d <= k? D: given n ...

18

Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful. Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single number that represents, in some sense, how does the typical element of $a$ look like. One way to do so is to take the average of the numbers in $a$, which roughly ...

18

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there is an important difference between energy needed to make a computation run, and entropy generated by the computation and put out into the environment, typically ...

16

I would like to add some more references to Scott's comment: Indeed, Clebsch-Gordan transforms (that you can think of as multi-register quantum Fourier transforms) are a useful tool in the design of quantum algorithms for non-Abelian hidden subgroup problems (HSPs). Clebsch-Gordan transforms were used by Greg Kuperberg and Oded Regev to solve the dihedral ...

15

Consider trying to make atomic guesses for an unknown random variable $X$ distributed over some finite set $A.$ In Shannon entropy, it is assumed that you can query bit by bit, i.e., if $A=\{1,\ldots,N\}$ you can ask: Is $X\in \{1,\ldots,N/2\}$ ? (assume $N$ even or use floor/ceiling functions) In crypto and some decoding scenarios this is not realistic. ...

15

This is a great question, Suresh! Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs the world, and under this assumption, there are quantum devices that generate genuine, true, information-theoretic randomness. However, imagine that you're ...

12

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it. Maybe your post will help motivate me to ...

11

Renyi entropy (of order 2) is useful in cryptography for analyzing the probability of collisions. Recall that the Renyi entropy of order 2 of a random variable $X$ is given by $$H_2(X) = - \log_2 \sum_x \Pr[X=x]^2.$$ It turns out that $H_2(X)$ lets us measure of the probability that two values drawn i.i.d. according to the distribution of $X$ happen to be ...

9

Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in user2917198's comment). Here is the reference: J. Watrous. An introduction to quantum information and quantum circuits. ACM SIGACT News 42(2): 52–67, 2011. https://cs.uwaterloo.ca/~watrous/Papers/IntroductionQuantumCircuits.pdf As pointed out ...

9

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state in Harrow, Hassidim, Lloyd's algorithm does not immediately give you ...

9

If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many explicit constructions of such codes, and you can find the basic ones in lecture notes of courses about coding theory. For example, you can find a description of ...

8

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See Farhi et al's paper Quantum Money from Knots, Mark Zhandry's paper Quantum Lightning Never Strikes the Same State Twice, Daniel Kane's paper Quantum Money from Modular Forms. In order to make ...

7

Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as: circuit-based quantum computing (CBQC) Adleman-Lipton model (a model for computing using DNA) Turing machine model (a model where computations are done with symbols on a tape) One can devise algorithms using ...

7

Short answer: No. There are really two separate issues to unpack here: Even if it worked exactly as advertised (which, as you might have heard, is somewhat disputed at present... :-) ), D-Wave's machine, by the company's own account, is only for adiabatic optimization. There's no particular reason to think that it could implement (e.g.) Shor's factoring ...

7

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse operator is applied to decrypt.) The resulting scheme is perfectly secure -- if the key is selected uniformly at random, then even an attacker who know a ...

7

I just ran the first state you suggest (i.e. the GHZ state with negative phase in the Hadamard basis). Basically what I did was to write a circuit which creates that state, apply one of 5 stabilizer generators (XIXII,IXXII,IIXXI,IIXIX or -ZZZZZ) and then inverted the creation process. The circuit is shown below for the -ZZZZZ stabilizer. There seems to be ...

7

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened with approximate MAX3LIN: a quanutm algorithm outperforming all previous known classical algorithms motivated a succesfull search for a better classical ...

6

I'm not sure who would suggest that qubits can meaningfully be described this way, or why anyone would do so. There are simply too many missing details, and it falls afoul of no-go theorems for local hidden-variable theories in quantum mechanics. This isn't "an exhaustive description of a digital quantum computer that uses a finite set of pure states to ...

6

We will never be able to prove this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell ...

6

I don't know of any function with communication much higher than the $\gamma_2$ bound. However, my intuition of why it is not tight is because the $\gamma_2$-norm is also a lower bound for QCMA communication. See this paper by Klauck for the definition of QCMA communication. To prove the lower bound on QCMA communication using the $\gamma_2$-norm you can ...

6

It is often mathematically very convenient to work with sub-normalized states independently of the question whether they have a direct physical meaning. However, you can always see them as states that are logically 'AND' with a certain event. For example, consider the c-q state $\rho_{XB} = \sum_x |x\rangle\!\langle x|_X \otimes \rho_B^x$ where $\rho_B^x$ ...

6

In http://arxiv.org/pdf/quant-ph/0303055v1.pdf, it is shown that the weak membership problem for the set of separable states is NP-hard. As you can see in Definition 6.2 (page 18), this amounts to deciding if a state has a separable decomposition up to accuracy $\delta$. If you want to convert this to a search problem, you can thus do so by using a $\delta$-...

6

Look at John Preskill's Lecture Notes; particularly Section 3.2. As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, so you no longer necessarily have a pure state of your system. For non-unitary quantum operations, if you assume that the environment doesn't remember ...

6

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time. But in context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you ...

6

The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae. Any circuit with an intermediate measurement can be converted to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again: Moving measurements onto a ...

6

It's not unitary, so it's impossible because all quantum transformations have to be unitary. Consider the states $$\frac{3}{5} |0\rangle + \frac{4}{5} |1\rangle \quad \mathrm{and} \quad \frac{3}{5} |0\rangle - \frac{4}{5} |1\rangle.$$ These get taken to  \frac{1}{\sqrt{2}}\left(e^{3/5 i} |0\rangle + e^{4/5 i} |1\rangle\right) \quad \mbox{and}\quad \...

5

I think this question is probably better suited to cs.stackexchange.com, and I hesitate to answer it. That single qubit gates are not universal was stated by Deutsch, Barenco, and Ekert in 1995. They point out that you cannot entangle un-entangled qubits with only single qubit operators. You can also prove this without any appeal to entanglement or states ...

5

This problem has been studied in great detail, not just for the case of imperfectly cloning 1 qubit to get 2 copies, but more general problems of how to get m copies of a state given n copies, etc. I don't work in the area, but I'll try to give you some answers. Others may be able to provide a better answer. For the problem you describe, 1 qubit to 2 qubit ...

5

The set of problems that can be solved by an universal quantum computer in "polynomial time" (with at most 1/3 probability of error) is called BQP. Travelling salesman problem is in complexity class called NP. Furthermore, it is NP-complete: meaning that if the Travelling Salesman Problem can be solved in any model of computation which can also simulate ...

Only top voted, non community-wiki answers of a minimum length are eligible