Is your application registered as a live one not test? (Yes… test should work but people have reported various issues).
Some people have also had issues with registering more than one API key and then using the wrong one, worth a double-check.
This exact endpoint (almost) works for us - although one note: it looks like you’re requesting:
https://api.company-information.service.gov.uk/advanced-Search/companies
With a capital “S” there - that will give a 404 error once you’ve sorted out the authorization issue. It should be:
https://api.company-information.service.gov.uk/advanced-search/companies
(Obviously also calling a search endpoint without providing some parameters is in general odd!)
Good luck.