Questions tagged [annealing]

It is a metaheuristic for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. (Wikipedia)

Filter by
Sorted by
Tagged with
1 vote
1 answer
34 views

How does Fujitsu's digital annealer work?

I have read Fujitsu's white paper for a brief introduction to their device: http://marketing.us.fujitsu.com/rs/407-MTR-501/images/quantum-inspired-computing.pdf As far as I know, Fujitsu's hardware is ...
user avatar
  • 33
1 vote
0 answers
19 views

How can a QUBO matrix with many identical, non-zero off-diagonal terms be made sparse?

I am with a QUBO matrix where entire off-diagonal sections are with the same value, which is the same between sections. Consider the following example (much smaller than those I am actually working ...
user avatar
3 votes
2 answers
47 views

Can D-Wave machines be applied to simulate Hamiltonians arising in quantum physics?

AFAIK D-Wave primarily advertises their machines as tools for solving problems with classical input, i.e. when the Hamiltonian to be minimized is a function of $Z$s. Can one use their machines in ...
user avatar
  • 1,478
2 votes
1 answer
61 views

Why is quantum annealing often associated with the Ising model?

Quantum annealing is often associated with Ising Model, in the sense that the problem Hamiltonian needs to be in the form of an Ising Hamiltonian. Is this because the physical description of the ...
user avatar
  • 441
2 votes
1 answer
31 views

Is there any rigorous proof that Quantum Annealing provides a quantum advantage?

Is there any rigorous proof that Quantum Annealing (QA) is of any benefit (e.g. in terms of time to optimal solution, convergence rate, etc.) for a specific problem? Or any empirical evidence for the ...
user avatar
0 votes
0 answers
10 views

QUBO formulation: tackle constraint with multiplication of two variables

Currently I have got the constraint like this $a+ab \leq1$ which can be reformulated to equality adding slack variable $(a+ab-1+slack)^2=0$. From now on, I can get all coefficients of the products ...
user avatar
1 vote
2 answers
65 views

Is digital quantum computing more powerful than the analog one?

What I get so far: Analog quantum computing: The Hamiltonian is implemented on the QC, solution is found by e.g. quantum annealing. The whole state is changing continuously. Digital quantum computing: ...
user avatar
  • 135
1 vote
1 answer
60 views

Convert Hamiltonian to Ising Formulation or QUBO

I have a tridiagonal Hamiltonian matrix that I need to convert to QUBO or Ising format to use D-Wave's quantum annealing solvers. For a generic tridiagonal: \begin{pmatrix} a_1 & b_1 \\ c_1 & ...
user avatar
4 votes
0 answers
33 views

Why do Quantum Annealer have (currently) a higher scaling potential?

One may categorize quantum computers in two classes: Quantum Annealer and (universal) Gate Quantum Computers. There may be also other categories. IBM announced 127 Qubits for their next Gate Quantum ...
user avatar
  • 141
2 votes
1 answer
42 views

Quantum Annealing vs Quantum Monte Carlo: can QMC do all that QA can?

I'm working on an essay about quantum technology, and the connection between the annealing algorithm and quantum computing hardware is an important transition in the text. I'd like to know if there is ...
user avatar
  • 33
1 vote
1 answer
45 views

Is the Quantum Annealing model universal?

I understand that the D-Wave Quantum Annealer they have today is not a universal quantum computer. Is the reason that it's not universal because of the lack of error correction and lack of all-to-all ...
user avatar
0 votes
0 answers
42 views

Mathematical definition of QUBO problem

The quantum annealing approach is using the equivalence between QUBO matrix and Ising Hamiltonian to solve the problem. Therefore, it is necessary to transform a NP-hard problem into a QUBO matrix. ...
user avatar
3 votes
1 answer
46 views

Can any binary problem be solved by a QUBO?

As far as I know, if a computing problem can be solved by the quantum annealing approach, it also means the solution space should be binary, e.g., a vector that only contains either 0 and 1. Otherwise,...
user avatar
4 votes
0 answers
42 views

Any simulator packages for quantum annealing/adiabatic quantum computation?

Are there any simulator packages for quantum annealing/adiabatic quantum computation, like Qiskit Aer but for quantum annealing? There seems to be only classical heuristics in D-Wave Ocean package, ...
user avatar
  • 166
3 votes
1 answer
110 views

What is the relationship between the mixing operators and initial states found in QAOA and Quantum Annealing?

In many papers, the QAOA is shown to be intimately related to Quantum Annealing/Quantum Adiabatic Algorithm/Adiabatic Quantum Optimization. The mixing operator in the QAOA is described by Hadfield as ...
user avatar
  • 41
2 votes
1 answer
91 views

Understand final Hamiltonian in Quantum Annealing

Currently, I’m studying quantum annealing in which the system evolves according to the Hamiltonian: $$ H(t) = H_F + \Gamma(t) H_D,\tag{1} $$ where $H_F$ is a final (classical) Hamiltonian, $H_D$ is a ...
user avatar
  • 133
2 votes
0 answers
47 views

Example of lower bound on spectral gap for adiabatic quantum computing

is there a list of reference for which the authors prove a lower bound of the spectral gap for an adiabatic quantum algorithm? I.e. I am searching for examples where the authors solve a problem with ...
user avatar
  • 453
1 vote
1 answer
125 views

How is eigendecomposition of a Hamiltonian equivalent to finding the minimum of an energy function?

This question is in regards to Dwave's quantum computer which is tailored to solve QUBO problems using quantum annealing. QM tells us that the ground state of a quantum system is given by the ...
user avatar
  • 349
1 vote
1 answer
52 views

Question about the counter diabatic(CD) term in Digitized Adiabatic Quantum Computing

Recently I have read two articles about the Digitized Adiabatic Quantum Computing(DAQC), and tried to factorize $35=5\times7$ and $2479=67\times37$. But some problems came when trying to solve the ...
user avatar
  • 21
3 votes
0 answers
50 views

What type of tasks it is possible to solve on a quantum simulator?

In this article, the author claimed that researches from Harvard and MIT created 256 qubits quantum simulator. However, we are not talking about piece of software on a classical computer but actual ...
user avatar
5 votes
0 answers
63 views

Quantum annealing - studies showing empirical evidence for better performance in comparison with classical computers

Currently, it is not known wheter quantum anneling or algorithms like VQE and QAOA for general purpose quantum computers bring about any increase in computational power. However, there are some ...
user avatar
1 vote
1 answer
44 views

What do the numbers in the Ising sampleset mean?

I am trying to create a portfolio optimization with the DWave Quantum Computer. I wrote some code trying to somehow reconstruct the following Ising model paper: Ai ...
user avatar
3 votes
0 answers
31 views

What is the state-of-the-art annealing device for solving Ising problems?

I understand that in addition to D-Wave's quantum annealer, there have been other unconventional (although non-quantum) Ising solvers like the one from Toshiba, Fujitsu, the Coherent Ising machine, ...
user avatar
  • 73
4 votes
1 answer
75 views

Is Quantum Annealing threatened by the Quantum Gates approach?

Since Quantum Annealing is extremely powerful for optimization it is limited in scope. However, when a universal Quantum Computer based on gates arrives, it will have a wider scope including ...
user avatar
3 votes
1 answer
68 views

How to decide bias in Hamiltonian Ising model?

I am trying to code finance portfolio optimisation problem into a quantum annealer, using the Hamiltonian Ising model. I am using the dwave module ...
user avatar
3 votes
1 answer
93 views

Relationship of Adiabatic Quantum Computing speedup to Quantum Random Walk hit time

Considering the following two phenomena: Adiabatic quantum computing in general exhibits a quadratic speedup over classical simulated annealing, though for some Hamiltonians it may be faster (while ...
user avatar
3 votes
1 answer
82 views

Why is it so important to have uniform chain lengths in a minor embedding?

Very brief background In quantum annealing, the discrete optimization problem we wish to solve (such as finding the minimum of $b_1b_2 - 3b_1 + 5b_3b_4$ for binary variables $b_i$) may have a ...
user avatar
12 votes
3 answers
2k views

Are spin-glass problems NP (-complete)?

It is well known that finding ground states for spin-glass systems (Ising, XY...) is NP-hard (at least as hard as the hardest NP-problems) so that they can be efficiently used to solve other NP ...
user avatar
  • 223
2 votes
1 answer
160 views

Adiabatic Quantum Computer e intermediate Hamiltonian evolves the state within the manifold

The Adiabatic Quantum Computer is implemented by slowly increasing the parameter s from 0 to 1 in the intermediate Hamiltonian $[\hat{H}(s) = \hat{H}_{input} + (1-s)\hat{H}_{init} + s\hat{H}_{circuit}]...
user avatar
  • 495
1 vote
2 answers
57 views

In quantum adiabatic simulation, is the $s$ in $(1-\frac{s}{T})H_{in}+\frac{s}{T} H_{cl}$ related to the $t$ in $e^{-iHt}$?

I just want to do a whole adiabatic calculation on quantum circuit. To prepare two Hamiltonian of $H_{initial}$ and $H_{classical}$ and solve $H_{classical}$ using adiabatic calc like quantum ...
user avatar
  • 11
9 votes
3 answers
291 views

What is the computational complexity of quantum annealing?

Quantum annealing can be thought of as a black box solver that can find approximate solutions to hard optimization problems. For example, D-Wave quantum annealers can approximately solve quadratic ...
user avatar
3 votes
0 answers
77 views

D-WAVE QUBO Matrix Form

I am trying to write down this problem (friend/enemy graph) in a polynomial matrix form in order to understand quantum annealing better, but it seems like the problem should actually be split into ...
user avatar
  • 31
4 votes
1 answer
283 views

Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?

Quantum annealers are single purpose machines allowing to solve quadratic unconstrained binary optimization (QUBO) problems. QUBO problems have following objective function: $$ F=-\sum_{i<j}J_{ij}...
user avatar
4 votes
0 answers
56 views

Is either the adiabatic or the diabatic version of quantum annealing known to be theoretically more powerful than the other?

Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "...
user avatar
  • 2,107
1 vote
0 answers
45 views

Is it absolutely necessary for Hamiltonians to not commute in QAA?

I have already read through the answers here. So I understand that if the Hamiltonians commute, then they have the same eigenstates but not necessarily the same energy eigenvalues. To formulate my ...
user avatar
3 votes
2 answers
676 views

What is an example of a simple QUBO problem?

I am digging into to the workings of the D-wave quantum annealing computers using this documentation. I find it very intuitive and well-explained, but their example of a "simple QUBO problem" does not ...
user avatar
4 votes
0 answers
145 views

How to convert a qubit hamiltonian to QUBO and vice versa?

This is my hamiltonian. Solving this by hand, Numpy Python package and VQE algorithm gives the minimum energy eigenvalue -2. If we want to find the minimum energy of this hamiltonian with Quantum ...
user avatar
3 votes
1 answer
91 views

Best route to learn quantum annealing as a beginner

My main goal is to learn Quantum annealing and quantum optimization in general. This concept is elaborated in this paper. A better example is this paper. I am particularly interested in reading ...
user avatar
1 vote
1 answer
99 views

Quantum Annealing - Random results on big N

I implemented a solver for the Job Shop Problem, based on quantum annealing, on a D-Wave machine. I have a problem, that even though minimal energy solutions exist, they are only chosen once. I set ...
user avatar
  • 107
2 votes
1 answer
84 views

Quantum Annealing - Job Shop Problem

using this paper, I want to implement a solution for the Job Shop Problem on a D-Wave machine. One of the constraints mentioned in the paper, is $$ h_3(\bar{x}) = \sum_i \left(\sum_t x_{i,t}-1 \right)^...
user avatar
  • 107
1 vote
0 answers
32 views

Entanglement and teleportation in quantum annealing and parallel computation

In classical optimization problems, some objective function's surface serves as a landscape for finding its minimum through minimization algorithms. Instead of your typical U-shaped objective ...
user avatar
5 votes
0 answers
52 views

Max eigenvalue algorithm via annealing starting from Gibbs state

In this talk, and the corresponding slides on page 24/44, Brandao talks about the max eigenvalue problem which is: Given a Hermitian $n\times n$ matrix $H$, approximate its largest eigenvalue. (Note ...
user avatar
  • 809
1 vote
1 answer
151 views

Minimum Spanning Tree on D Wave Processor

I am attempting to implement a minimum spanning tree problem on the D wave quantum computing architecture. I have seen many graph problems implemented, such as a graph coloring example. There are also ...
user avatar
4 votes
2 answers
83 views

What does it mean to have 2000 qubits and 6016 couplers?

From official D-Wave docs: The D-Wave 2000Q QPU has up to 2048 qubits and 6016 couplers. For example, I have the optimization problem defined as the QUBO problem. If I want to solve it on D-Wave,...
user avatar
5 votes
0 answers
83 views

How to calculate the $r^{\text{th}}$ digit of $\sum ^{j−1}_{p=i}d^p_{\pm k}$ using PyQUBO?

I am going to implement "turn circuit encoding" method of Coarse-grained lattice protein folding on a quantum annealer(Babej, Ing & Fingerhuth; 2018) using PyQUBO to run on the DWave qbsolv ...
user avatar
1 vote
1 answer
63 views

Is there an inherent difference in need for error correction between quantum annealing and gate based methods?

When I read about computing using gate based methods, I mainly read about the difficulties with error rates, circuit depth (and connectivity) and not enough qubits. With computing using quantum ...
user avatar
1 vote
1 answer
75 views

Q1Q2Q3Q4 coupling in qubo file

According to the question Q1Q2Q3 coupling in qubo file we can couple 3 qbits. When it comes with 4 qbits like q1q2q3q4, how should set this 4-qbit element to qubo file?
user avatar
1 vote
1 answer
95 views

Q1Q2Q3 coupling in qubo file

When we expand the Ising model we have one component with 3 qbits like Q1Q2Q3. But in qubo file we can only set coupling for 2 qbit only. How should I set this 3-qbit element to qubo file?
user avatar
1 vote
0 answers
34 views

What are techniques are used to esimate the spectral properties of annealer embedding hamiltonians?

Some information about the spectral properties of the hamiltonian of a given annealer emebedding is needed to determine a proper annealing schedule, correct? What are methods that are used to find ...
user avatar
5 votes
2 answers
138 views

Are there established best practices for designing Dwave embeddings?

Some of my larger annealer embeddings (~200 qubits) don't anneal down to the ground state while some of them do very easily. Are there established guidelines for designing annealer embeddings to ...
user avatar