Algorhythms: Generating Music with D-Wave’s Quantum Annealer
In this Blog we will be discussing our project for the iQuHack 2021 Hackathon.
Abstract
The creation of good music has been a coveted talent for centuries. Making a good song is quite difficult as one must know all the notes and which notes to play after the other in order to produce a ‘banger’. As a society we have long relied on talented people to bring us the joy of music. We however, have challenged those individuals by successfully writing an algorithm that creates music while minimizing the dissonance between the notes. Using the D-wave Leap Sampler we applied the rules of music theory to a Markov Random Field in order to optimize the quality of the music and minimize the dissonance from one chord to another. Furthermore we translated the raw music we created into a playable file for all to experience quantum music using our custom CLI.
Motivation and Goals
Our primary goal was to use quantum computing to create something amazing. We decided on music because we had not heard of anyone using quantum annealing to optimize the creation of music. Another reason we chose to explore music is because it is the universal language. Imbuing a program with the ability to write a universal language is in our opinion, amazing.
On a more technical note, inspired by this paper, we became interested in markov chain monte carlo processes and stochastic processes on quantum annealers, and sought to simulate a random walk on such a machine on a quantum annealer, which has not been done yet. This opens the door for more computationally heavy stochastic processes to be implemented on quantum annealers.
Background
We begin with some background information on quantum annealing processors, some music theory, and some Markov chains.
Quantum Annealing processors return low energy solutions. There are two types of models Optimization and Sampling, of which we chose sampling. The Sampling solver samples from many low energy states and chooses a good candidate for a set of low energy states.
Dimod — https://docs.ocean.dwavesys.com/en/stable/docs_dimod/intro/index.html
Dwave Networkx — https://docs.ocean.dwavesys.com/en/stable/docs_dnx/intro.html
Ocean Setup — https://docs.ocean.dwavesys.com/en/stable/getting_started.html
Dwave Quantum Solvers -https://docs.ocean.dwavesys.com/en/stable/overview/qpu.html
What is Quantum Annealing? — https://docs.dwavesys.com/docs/latest/c_gs_2.html
Some Music Theory
Music has a lot of distinct options for rules so we combined some classical compositional techniques with modern jazz theory to put constraints on our optimization function which allows for edge weighting on our Markov chain states. Classically when generating music you are looking for music that moves. So you want music that starts somewhere and moves chord to chord in a fashion that follows some rules. The most important rules consist of restricting which notes should be played in succession. For example playing a G chord resolves nicely to a C chord while a G chord does not resolve nicely to an F minor chord.
Some interesting resources for further reading:
Mick Goodrick — The Advancing Guitarist
Ed Friedland — Building Walking Baselines
Vincent Persichetti — 20th-Century Harmony
Dave Liebman — A Chromatic Approach to Jazz Harmony and Melody
Markov Chains
A Markov Chain is a graph that is used to represent state machines. It consists of nodes, representing states, and edges representing the transitions between those states. The edges can be weighted, and oftentimes represent the conditional probabilities of transitioning from one state to the next.
A simple Markov Chain for states GG, Gg, gg, with transition probabilities.
This is relevant to music generation, since we can encode the desired notes or chords as states, and using some basic music theory, define edges and transition probabilities between chords that should be played in succession. Here’s an example Markov chain for some notes:
An example Markov Chain for some notes
Now how can we generate music with this Markov Chain?
Random Walks
It’s simple! We can perform a ‘random walk’ on the matrix. We start with a given state, and using the transition probabilities, we can determine which state to go to next. This process has no memory — only the current state is ever taken into consideration. Random walks and other algorithms such as Markov Chain Monte Carlo (MCMC) are very powerful for stochastic simulations, and in our case, creating random music (that still abides by the laws of music theory)!
A simple song would consist of many iterations of jumping between notes or chords.
Markov Random Fields
In order to implement a random walk or MCMC using D-Wave’s samplers, however, we have to change our setup just a bit in order to formulate it as an optimization problem. This can be done using Markov Random Fields, which define relationships between and dependencies between vertices, instead of transition probabilities. Each edge (a, b) can be one of 00, 01, 10, 11, indicating the binary values of its vertices. Each one of those states is associated with a potential energy, and our objective is now to find the lowest energy state of the entire Markov network.
A simple Markov Random Field with undirected edges, with vertex dependencies
Luckily, dwave_networkx allows us to do just that! We created the following Markov Random Field for the chords I, II, III, IV, V, VI, VIIdim:
Our Markov Random Field
Defining the potentials with dwave_networkx is easy:
>>> potentials = {(‘a’, ‘b’): {
(0, 0): -1,
(0, 1): .5,
(1, 0): .5,
(1, 1): 2},
… (‘b’, ‘c’): {
(0, 0): -9,
(0, 1): 1.2,
(1, 0): 7.2,
(1, 1): 5}}
>>> MN = dnx.markov_network(potentials)
>>> sampler = dimod.ExactSolver()
>>> samples = dnx.sample_markov_network(MN, sampler, fixed_variables={‘b’: 0})
>>> samples[0] # doctest: +SKIP
{‘a’: 0, ‘c’: 0, ‘b’: 0}
The desired states are assigned lower potentials. In this examples, the lowest energy state assigns 0 to each node in the network.
In order to benefit from the sampler and introduce stochasticity, we decided to randomly assign potentials, as in the example below with 3 chords:
{(‘I’, ‘II’): {
(0, 0): 10,
(0, 1): -9.720022593351157,
(1, 0): -3.264126577542288,
(1, 1): 10
},
(‘I’, ‘III’): {
(0, 0): 10,
(0, 1): -7.664969424108326,
(1, 0): -2.8128625691633147,
(1, 1): 10
}}
We consider the 1 state to be the chord being played. The (0,0) and (1,1) edges were assigned an arbitrarily high potential energy to avoid states where the current note is played again, or two notes are played simultaneously.
How it works
Our algorithm works by creating a random distribution of potentials for the chord Markov Random Field for each chord we want to generate, and then sampling that distribution for the lowest energy state. The chord with the lowest potential is our next chord! This is done for each chord. We then encode the chords into a MIDI file, which is returned by the user, and can be opened in software such as MuseScore in order to play it back, and even see the musical score!
Localized simulator example — https://www.youtube.com/watch?v=KgYJ4NS7EHU
The demo above demonstrates using our Algorhythms CLI to generate a song using a the local `ExactSolver` D-Wave sampler. The CLI can also be configured to use D-Wave’s Leap Hybrid Solvers, in which case the music will be created directly by the quantum annealer!
Dwave Markov — https://docs.ocean.dwavesys.com/projects/dwave-networkx/en/latest/reference/algorithms/markov.html
Results
We were able to successfully code our algorithm to create its own music. Furthermore we developed a friendly CLI to create the name of the song and the length of the music in seconds.
This is an example of a localized quantum generation that our program created. The project is easily scalable to a theoretically infinitely long song that can be played in any key. The program runs, calculates, and then writes a MIDI file that can be played in almost any audio output (such as Windows Media Player or MuseScore). Lastly, we were able to claim a victory in our division of the Hackathon!
Lessons Learned
- Setting the potential energies manually is too time intensive for a Hackathon. We decided to randomize the probability distributions to save time. This could be an interesting space for future fine-tuning and exploration.
- Setting up a Quantum sampler and researching applications to Markov Field Theory and Markov Networks.
- “Working with Rami is awesome” — Alex and Jake (big lessons) ❤
Next Steps
We would like to add rhythm and melody to the generated chords, and explore more complex stochastic processes for generating music!
- Melody and Rhythm
- Erik Demaine and William Moses have famously identified several important NP-hard problems in music arrangement, which would be interesting future problems to tackle using quantum annealers
- Create music that is influenced by different genres. For example have a classical filter so the created music resembles that of classical artists.
Concluding Thoughts
Participating in the hackathon was a blast. It was a lot of fun to see all of the awesome ideas that the other teams came up with and the approach they took to implement them. All three of us were very happy with the outcome and scalability of our project. Winning was an added bonus!
Check out our competition github:
https://github.com/iQuHACK/2021_Algorhythms
We also maintained an updated repo:
