6

For the specific linear function you are interested in, the solution turns out to be trivial: you can take the channel to be $N_{X\rightarrow Y}(\rho) = \operatorname{Tr}(\rho) |\psi\rangle\langle \psi|$ for $|\psi\rangle$ being an eigenvector of $\sigma_Y$ having the largest possible eigenvalue. More generally, however, you can optimize any real-valued ...


6

As requested in the comments, here is a worked example. The main body deals with minimizing $f(x)$ for a specific problem. At the bottom follows a brief discussion of constraints then a brief discussion about the general case. Let's solve the Weighted Maximum Cut problem since this Is a relatively straight-forward example Is hard classically Is a ...


4

First: The paper references [37] for Levy's Lemma, but you will find no mention of "Levy's Lemma" in [37]. You will find it called "Levy's Inequality", which is called Levy's Lemma in this, which is not cited in the paper you mention. Second: There is an easy proof that this claim is false for VQE. In quantum chemistry we optimize the parameters of a ...


4

So for hybrid quantum-classical algorithms, I suggest looking at : The Quantum Approximate Optimization Algorithm Variational hybrid quantum-classical algorithms that include the so famous Variational Quantum Eigensolver applied for Max-Cut problems PennyLane which helps you in developping hybrid computation for optimization problems and Machine Learning. ...


4

What motivated this construction is mentioned in the original paper (section VI): adiabatic quantum computing. This construction is basically a Trotterized version of the evolution by the time dependent hamiltonian: $$ H(t) = (1-t/T)B + (t/T) C $$ where T is the total runtime. The Trotterized evolution consists of alternately applying $U_{C}$ and $U_{B}$. ...


4

The proof of the variational theorem (the theorem that the ground state energy is the lowest possible energy you can get from $\frac{\langle \psi|H|\psi\rangle}{ \langle \psi | \psi \rangle}$) is very simple: https://en.wikipedia.org/wiki/Variational_method_(quantum_mechanics) If you get a lower energy, it means you don't actually have $\frac{\langle \psi|...


4

Short Answer: It is potentially hard (as bRost03 indicates in the comments). To be precise, coNP-hard. Longer Answer: In adiabatic quantum computation, the ground-space of the final Hamiltonian is typically determined by the optimum solution to some constraint satisfaction problem (CSP). If the CSP is perfectly solvable, the ground-space is spanned by (...


3

If you are looking for a more complete implementation of a quantum variational algorithm in the context of Cirq, I would recommend looking at the second example in the OpenFermion-Cirq notebook found here. It uses a custom ansatz for hydrogen in a minimal basis, but makes a bit more explicit all the required pieces. Another good example, perhaps without ...


3

Here is the best circuit I've found. It uses 14 CNOTs. Note that this circuit is not using a linear layout! It is placed on the grid like this: 0-A-1 | 3 | 2 Where 'A' is an ancilla initialized in the |0> state and '0','1','2','3' are the qubits making up the register (with '0' being the least significant bit). I verified this circuit in Quirk ...


3

Here is the best construction I've found. It uses 8 CNOTs. I verified this circuit in Quirk using the channel-state duality and a known-good inverse. The target is the middle qubit. None of the CNOTs go directly from top to bottom or bottom to top. You can switch which qubit is the the target by simply switching which line the Hadamards are on.


3

I believe I've got it down to 9 controlled-not gates: What I did was I used a set of three cNots in the place of Swap to move the two controls next to each other to achieve the last part of the standard Toffoli circuit (see here). This used 12 cNots. However, the final $T$ and $H$ gates on the target qubit I propagated through one of these swaps. This let ...


3

I am not an expert but I read a few papers and here is what I have found. Similarly to NN, people found strategies to avoid this issue with the gradients. Basically, for some problems, you can use ansatzes that are inspired by the physics of the problem itself. For example, in quantum chemistry, people use something called unitary coupled clusters. See ...


3

The Quantum Approximate Optimization Algorithm is a good place to start for analyzing the relative performance of quantum algorithms on approximation problems. One result so far is that at p=1 QAOA can theoretically achieve an approximation ratio of 0.624 for MaxCut on 3-regular graphs. This result was obtained using brute force enumeration of the different ...


3

One of the advantages, as stated in the paper you linked, is that with QAOA you can increase the precision arbitrarily, whereas QA will only find the solution with probability 1 as $T \to \infty$ which is impractical. In addition if $T$ is too long you're likely to not find the solution as the probability is not monotonic. I believe an example of this can be ...


2

I suggest looking at how a genetic algorithm works in a context of discrete variables to understand it. They provide a methodology but you can apply other mutation/crossover techniques. Briefly, in a simple optimization problem where the variables are discrete, we can solve heuristically with genetic algorithms (which belongs to the class evolutionary ...


2

There is currently no way to check the status of a job in Qiskit Aqua: https://github.com/Qiskit/qiskit-aqua/issues/545 However, it looks like it is a feature that is coming.


2

Here is tested code (also provided in one of the qiskit tutorials) lapse = 0 interval = 60 while not job.done: print('Status @ {} seconds'.format(interval * lapse)) print(job.status) time.sleep(interval) lapse += 1 print(job.status) where interval is giving in seconds (if your job requires longer waiting and execution, I would suggest to ...


2

So in your example, you try to find the quantum circuit representing the Toffoli operation. I would then change my objective/fitness function and compare the unitary matrix representing the operation. You can use an minimization objective like : $$ \mathcal{F} = 1-\frac{1}{2^n} |\operatorname{Tr}(U_aU_t^{\dagger})| $$ with $ U_a $ is the unitary of the ...


2

I will try to give you a hint how to rewrite your problem as an binary optimization problem which can be solved on quantum annealer, i.e. a single purpose quantum computer for solving optimization task (see more about annealers here). Your problem as an binary assignment problem: Lets denote $x_{ik} \in \{0;1\}$ a binary variable meaning whether a person $i$ ...


2

Based on comment by DaftWullie and my experience with the algortihm, it seems that a title of the article is misleading. The authors claim that algorithm they proposed is efficient. However, this is true only partialy. The authors devised only part of an algorithm for solving TSP. In particular, they are able to calculate length of a Hamiltonian cycle ...


2

In the article you mentioned it is said that classical algorithms can beat some cases of (quantum ) QAOA's as is proved in this article. So finding cases where quantum QAOA can still beat classical algorithms and can run on NISQ devices with low depth circuits is still exciting and promissing. The article uses plausible conjectures from complexity theory to ...


2

The objective of the portfolio optimization problem is to trade off expected return ($\mu^T x$) with the risk taken ($x^T \Sigma $x). This could be achieved by introducing a constraint on the risk, e.g. $x^T \Sigma x \leq R$, for an acceptable risk level $R$ and then maximize the return under this constraint. However, this is not a QUBO, i.e., it cannot be ...


2

Maybe this will help. Let's take a simple case: $$f(x_1, x_2) = -2x_1 x_2$$ Then it is minimum when $x_1 = x_2 = 1$. Now let's take this Hamiltonian: $$H_f = -2Z \otimes Z$$ The Hamiltonian is minimum when we have either $|00\rangle$ or $|11\rangle$ states. So this Hamiltonian doesn't correspond to the $f(x_1, x_2)$. Instead this one looks better: $$H_f ...


2

These levels are provided via "preset passmanagers" in Qiskit. These are simple-to-use transpiler pipelines, but you can also build your own passmanager pipeline. You can see what each does by inspecting the documentation for those: https://github.com/Qiskit/qiskit-terra/tree/master/qiskit/transpiler/preset_passmanagers But briefly, level 0 does no explicit ...


2

In the web based composer there is currently no way to adjust the optimization level. As a workaround, you can put a barrier before and after each gate. This will prevent them from being joined.


1

For each trial SPSA evaluations the objective function twice for + and - some small delta. Hence its total calls to the objective function are twice the max trials number. COBYA makes one evaluation for each iteration, that is what it's behavior is. Other optimizers, that are gradient based, where it's using finite difference method, will make many calls, ...


1

The Ising model is a formulation of your problem. Variables are variables $s_i$ that can take +1/-1 values. $$ \begin{equation} \text{E}_{ising}(s) = \sum_{i=1}^N h_i s_i + \sum_{i=1}^N \sum_{j=i+1}^N J_{i,j} s_i s_j \end{equation} $$ For a quantum form, we use spin operators $\sigma^z$, giving you an Ising Hamiltonian, whose eigenvalues correspond to the ...


1

From what I understand, $x_{i,t}$ are the binary variables. So your QUBO matrix should not be indexed as Q[i][t]. If you do this way, this means you have a binary variable $x_i$ and a binary variable $x_t$ and they have a real coefficient, so representing a term $Q[i][j] *x_i x_j$. In this case, if you really want a QUBO matrix with a correct indexing, you ...


1

Let's answer my own question: it is not possible. After some research I ended up computing the "truth table" for the two possible cases: $b = 0$: $\vert 00 \rangle\rightarrow\vert 00 \rangle$ $\vert 01 \rangle\rightarrow\vert 10 \rangle$ $\vert 10 \rangle\rightarrow\vert 10 \rangle$ $\vert 11 \rangle\rightarrow\vert 01 \rangle$ $b = 1$: $\vert 00 \...


1

Pedro! I assume you are familiar to Grover's algorithm. Therefore, I suggest to read carefully these two papers below: 1) Tight bounds on quantum searching (BBHT): it's a very broad Grover's algorithm analysis; 2) A quantum algorithm for finding the minimum (DH): this is the first Grover's algorithm application to optimization problems and we call DH (...


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