Estimating Quantum Volume for Advantage

IBM invented quantum volume to compare quantum computers across architectures.

IonQ claims a 2^22 quantum volume for its latest 32-qubit computer.

I come up with an idea to estimate the quantum volume for Advantage with the TSP problem:

Quantum volume is a new metric proposed by IBM to compare different quantum computers and their reliability [1]. 
We allow us to reinterpret this metric as follows: what is the volume span by the maximal number of qubits in a chip operating which do operate completely error-free and are fully interconnected? So the logarithm in base 2 of the quantum volume can be interpreted as the number of qubits fully interconnected, operating error-free.

With this reintepretation of quantum volume, we can run the Travelling Salesman Problem (TSP) on DWave's chips and get an estimation for the quantum volume. TSP requires for N-cities a complete graph K_N^2 as each city is hotcoded with N-Qubits (city 1: 0....1, city 2: 0...10, city N: 1...0). So N cities where each city is hotcoded with N qubits requires N^2 qubits and this N^2 qubits need to be fully interconnected with each other in a complete graph K_N^2. On the interconnections the distance matrix (NxN) is applied. In other words each interconnection gets a weight attached to it, corresponding to the distance between two nodes. DWave's Ocean suite then remaps the fully interconnected graph to the less connected Pegasus graph of Advantage (or to the even less connected Chimera graph) using way more qubits.

If we launch the TSP problem with the source code available here by Bohr Techonlogy on DWave's Leap platform and we add just some tweaks to punish incorrect solutions (too short by not visiting all cities or too long when visiting cities twice),
and then run it on the bare quantum chip (no hybrid things) we receive the following results:

The Dwave chip DW_2000_Q6 calculates the exact solution for 4 cities, but fails with 5 [3]. So number of qubits working precisely is for sure greater than 4^2=16 and for sure lower than 5^2 (25). The quantum volume itself is for sure at least 2^16=65'536 but below 2^25.

The Dwave chip Advantage_system1.1 calculates the exact solution for 6 cities but fails with 7 [4]. The number of qubits working precisely and fully interconnected is 6^2=36 but for 7^2=49 we get an incorrect solution. The quantum volume for Advantage is at least 2^36= but below 2^49.

IonQ currently claims a 2^22 quantum volume [2], so at least in my intepretation Advantage is far better while DW_2000_Q6 might lay behind.

Do you think my interpretation of quantum volume is correct?

 

 

 

One difference with our approach and the IBM one [1] which makes our lower bound more optimistic is that we choose the best proposed solution from Advantage while in [1] it is looked at the percentage of correct solutions over a certain threshold.

We might change the quantum volume reinterpretation sentence by adding "for which at least one solution in the sample is optimal", but this would invalidate IonQ and IBM calculations so far and make the quantum volume for them greater. If we leave the reinterpretation as it is, Advantage Quantum Volume should be lower than 2^36...

As a complete graph with 180 nodes is embeddable directly in the Pegasus graph of the QPU, we can see them as 180 logical qubits fully interconnected. If they would operate error free, the theoretical quantum volume span by Advantage would be 2^180. 

[1] Measuring Quantum Volume 

[2] IonQ Releases A New 32-Qubit Trapped-Ion Quantum Computer With Massive Quantum Volume Claims

[3] Below the log of the achieved results on DW_2000_Q6 (2041 Qubits, Chimera graph):

N=4 QPU DW_2000Q_6
Brute force: [0, 1, 2, 3] 19.25965669651482
DWave: [1, 0, 3, 2] 19.25965669651482

N=5 QPU DW_2000Q_6
Brute force: [0, 3, 4, 1, 2] 24.883972062212624
DWave: [2, 4, 3, 1, 0] 32.74600931766605

[4] Below the log of the achieved results on Advantage_system1.1 (5436 Qubits, Pegasus graph):

N=5 QPU Advantage_system1.1 
Brute force: [0, 3, 1, 2, 4] 18.084364670329673
DWave: [1, 3, 0, 4, 2] 18.084364670329673

N=6 QPU Advantage_system1.1 
Brute force: [0, 3, 4, 2, 1, 5] 20.25544329378932
DWave: [1, 2, 4, 3, 0, 5] 20.255443293789323

N=7 QPU Advantage_system1.1 
Brute force: [0, 1, 3, 6, 5, 4, 2] 23.21220870271781
DWave: [5, 1, 0, 3, 2, 4, 6] 32.50901939330402

 

0

Comments

7 comments
  • Sometimes it gets also 7 cities right!

    N=7 QPU Advantage_system1.1 
    Brute force: [0, 1, 5, 4, 3, 2, 6] 26.124877873315285
    DWave: [4, 5, 1, 0, 6, 2, 3] 26.124877873315285

    0
    Comment actions Permalink
  • Hi Tiziano,

    Thank you for sharing your thoughts on applying IBM's concept of quantum volume to our system. Your approach is quite interesting!

    IBM's Quantum Volume metric is based on measuring gate error rates and combining those measurements to estimate error rates for a full size computation involving a random quantum circuit.    Since quantum annealers don't have gates, and since they use Hamiltonians to solve the whole problem at once rather than gate-by-gate,  it is not possible to compute QV directly on a quantum annealing system.

    That being said, the stated purpose of QV is to estimate how well a given quantum circuit would perform at solving ``full size'' problems.   One convenient property of quantum annealing is that you can measure directly how well the QPU does at solving full sized problems, instead of trying to estimate it from low-level (qubit and coupler) measurements.  Measuring QV based on TSP performance is an interesting approach to addressing that question.  But note that changing the problem from TSP to other problems would give wildly varying values of QV, and it would be hard to say which one is the ``right one.''

    As for solving the TSP problem on Advantage, I'm surprised you can only solve a problem with up to 7 cities. Are you sure your code is running on Advantage_system1.1 and not the D-Wave 2000Q system? I can embed a problem with 14 cities using Ocean's TSP tools and find_embedding. I haven't spent the time tuning chain strength and the problem parameters to get a good solution, but I hope that helps for now.

    On that note I took a look at the code you ran. It doesn't look like the chain strength value is optimal, so as you scale the problem up I suggest checking out this whitepaper on tuning chain strength.

    0
    Comment actions Permalink
  • hi Alex,

    thank you for your patience and clear explanation, my thoughts were in fact a bit wild, I apologize. Now I realize that as you say one problem is that QV would depend on the polynomiality/complexity of the algorithm that translates the original NP problem (TSP, knapsack, etc.)  to the Ising QUBO. 

    For the code I was using, it is very old and I did not tune chain strength at all. Or maybe I did some tuning one and a half year ago, but for sure not systematic. Now I was merely reusing it without changes. I know, it is not a professional approach, but I enjoy experimenting with Advantage in the little time left! *

    I am a bit surprised you can directly embed 14 cities meaning K_14^2 or K_196. From the slides I have (also old ones), the maximal complete graph that can be embedded on P16 QPU is K_180. I would expect the maximal TSP to be embedded with 13 cities (= K_169). But maybe the embedder does some more tricks to get TSP embedded even with 14 cities...

    best regards

    * I submitted once a random bit generator quantum circuit to the IBM's platform with one single Hadamard gate and waited one week for the result. This is no fun :-)

    0
    Comment actions Permalink
  • Hi Tiziano,

    You don't need to apologize! Your thoughts are quite interesting and stimulated some good discussion at D-Wave. So thank you for sharing. 

    I noticed the github repo didn't have any recent activity and wondered if that was the case. 

    The TSP algorithm we use in Ocean represents the TSP problem with a cartesian graph instead of a clique. My latest run of a 14 city TSP problem used 4151 qubits to embed the problem. I added the problem and embedding below in case you were interested in seeing what that looks like. 

     

    0
    Comment actions Permalink
  • The 14-city problem Burma14 in the TSP Library could not be embedded onto Advantage by D-Wave embedding software.  I made several attempts.

    Reference [1] says in II A 1 "the largest fully connected problem that can be embedded onto the 2000Q has approximately 60 spins, while the limit in practice depends on the number of faulty physical qubits in the device."  Since 8^2 > 60, 8-city TSPs are not expected to be embedded onto 2,000Q, but many 7-city TSPs can be.  This has been my experience.

    [1] E Grant, TS Humble and B Stump, Benchmarking quantum annealing controls with portfolio optimization, Physical Review Applied 15, 014012 (2021)

    0
    Comment actions Permalink
  • Hi Richard,

    I believe what you meant was “The 14-city problem Burma14 in the TSP Library could not be embedded onto 2000Q by D-Wave embedding software.” Then you referenced 2000Q limitations.

    A 14-city TSP should work on the current Advantage system since there's a working 48-city TSP demo which I was able to run without any issues (in the Leap Jupyter notebooks section).

    0
    Comment actions Permalink
  • Hello Mohammad,

    My comments are about quantum only solutions after an embedding, not hybrid. The solution of the 48-city TSP demo was hybrid.

    I would like the numbers for Advantage that are in my Reference [1] for the 2000Q processor. 

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post