Faits:
A.
Le 18 janvier 2010, Q._ s'est inscrite au chômage et un délai-cadre d'indemnisation de deux ans lui a été ouvert à partir du 1 er février 2010.
Par décision du 18 octobre 2011, l'Office régional de placement de la Riviera (ORP) a prononcé une suspension du droit à l'indemnité de l'assurée pour une durée de 5 jours, au motif qu'elle n'avait pas remis ses recherches d'emploi du mois de septembre 2011 dans le délai légal, soit le 5 octobre 2011 au plus tard.
L'assurée a formé opposition à la décision de suspension. Elle a indiqué qu'elle avait demandé à sa mère de déposer ses recherches d'emploi dans la boîte aux lettres de l'ORP le 4 octobre 2011, compte tenu du fait que les bureaux étaient déjà fermés. Le même jour, sa mère avait également déposé la feuille IPA (indications de la personne assurée) de l'assurée à la caisse de chômage située dans le même immeuble que l'ORP. Ce n'est que le 13 octobre suivant, lors d'un entretien avec sa conseillère ORP que l'assurée avait appris, à son grand étonnement, que ses recherches d'emploi n'étaient jamais parvenues à l'ORP alors que sa feuille IPA avait bien été réceptionnée.
Le Service de l'emploi du canton de Vaud (ci-après: le service de l'emploi) a écarté l'opposition dans une nouvelle décision du 9 février 2012.
B.
L'assurée a recouru contre cette dernière décision devant la Cour des assurances sociales du Tribunal cantonal du canton de Vaud.
Le tribunal cantonal a recueilli le témoignage de la mère de l'assurée. Selon les déclarations de celle-ci, comme elle l'avait déjà fait à plusieurs reprises pour sa fille, elle était allée apporter deux enveloppes, l'une à l'ORP et l'autre à la caisse de chômage. Ces deux institutions étaient logées dans le même immeuble au troisième étage. La mère de l'assurée a indiqué avoir mis les enveloppes dans les boîtes aux lettres respectives se trouvant à l'étage.
Statuant le 28 mai 2013, la juridiction cantonale a admis le recours et annulé la décision sur opposition du 9 février 2012 ainsi que la sanction litigieuse.
C.
Le service de l'emploi interjette un recours en matière de droit public contre ce jugement, en concluant à son annulation et à la confirmation de sa décision sur opposition.
Q._ conclut au rejet du recours, tandis que le Secrétariat d'Etat à l'économie a renoncé à se déterminer.

Considérant en droit:
1.
Le recours en matière de droit public (art. 82 s. LTF) peut être formé pour violation du droit selon les art. 95 et 96 LTF. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Le recourant ne peut critiquer la constatation de faits importants pour le jugement en cause que si ceux-ci ont été établis en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte (art. 97 al. 1 LTF), c'est-à-dire insoutenable, voire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause.
2.
Il est constant qu'une suspension du droit à l'indemnité d'un assuré peut être prononcée si les preuves des recherches d'emploi ne sont pas fournies dans le délai prévu par l'art. 26 al. 2 OACI (RS 837.02; voir <ref-ruling>).
En l'espèce, l'assurée a allégué que sa mère avait déposé le formulaire de ses recherches d'emploi (pour le mois de septembre 2011) dans la boîte aux lettres de l'ORP le 4 octobre 2011. L'ORP dit ne pas avoir reçu cette liste.
3.
Le principe inquisitoire, applicable en droit des assurances sociales, dispense les parties de l'obligation de prouver, mais ne les libère pas du fardeau de la preuve: en cas d'absence de preuve, il s'agit de savoir qui en supporte les conséquences. En matière d'indemnités de chômage, l'assuré supporte les conséquences de l'absence de preuve en ce qui concerne la remise des pièces nécessaires pour faire valoir le droit à l'indemnité, notamment la liste de recherches d'emploi (cf. arrêt C 294/99 du 14 décembre 1999 consid. 2a, in DTA 2000 n° 25 p. 122; cf. aussi arrêt 8C_591/2012 du 29 juillet 2013 consid. 4).
4.
En l'espèce, le premier juge a considéré que les déclarations de la mère de l'assurée étaient crédibles dès lors qu'elles étaient corroborées par le fait qu'il n'y avait pas eu de contestation s'agissant de la remise de la feuille IPA à la caisse de chômage, dont l'entrée était adjacente à celle de l'immeuble où se trouvait l'ORP (rue des Bosquets 31, respectivement 33). Dès lors, la preuve du respect du délai de l'art. 26 al. 2 OACI était rapportée au degré de la vraisemblance requise.
5.
5.1. Le recourant fait tout d'abord valoir que le témoignage de la mère de l'assurée n'était pas apte à prouver la remise en temps utile des recherches d'emploi de cette dernière. Le fait que la feuille IPA, déposée dans la boîte aux lettres de la caisse de chômage adjacente à celle de l'ORP, est bien parvenue à son destinataire ne permettait en effet pas de tenir pour acquis que les recherches d'emploi avaient elles aussi été déposées en temps utile.
5.2. L'argumentation du recourant revient ici à se plaindre de la manière dont la juridiction cantonale a apprécié les preuves.
L'appréciation des preuves est arbitraire lorsqu'elle est manifestement insoutenable, en contradiction avec le dossier, ou contraire au sens de la justice et de l'équité ou lorsque l'autorité ne tient pas compte, sans raison sérieuse, d'un élément propre à modifier la décision, se trompe sur le sens et la portée de celui-ci ou, se fondant sur les éléments recueillis, en tire des constatations insoutenables (<ref-ruling> consid. 4.2 p. 234; <ref-ruling> consid. 4.2 p. 560).
En l'occurrence, le recourant prend pour seul motif de ses critiques à l'adresse de la manière dont le juge précédent a retenu les faits un degré de certitude ou de vraisemblance prétendument insuffisant. Il n'expose en revanche d'aucune manière en quoi l'appréciation en question serait arbitraire. Quoi qu'il en soit, la circonstance que le témoin est la mère de l'intimée n'exclut pas d'emblée que sa déposition soit tenue pour digne de foi. Le tribunal cantonal a d'ailleurs expliqué les raisons pour lesquelles il accordait crédit au témoignage de la mère. Ce point de vue est défendable et s'inscrit dans le pouvoir d'appréciation du juge cantonal, même si la solution contraire n'aurait pas non plus été insoutenable (cf. arrêt 8C_591/2012 du 29 juillet 2013). Il échappe par conséquent au grief de l'arbitraire.
5.3. C'est en vain que le recourant se réfère à l'arrêt 8C_45/2012 (recte: 8C_46/2012). Dans l'arrêt précité, il était question de l'appréciation des allégations de l'assurée elle-même. Or, cette situation est différente de celle du cas d'espèce, de sorte que le recourant ne saurait rien en tirer.
6.
Vu ce qui précède, le recours se révèle mal fondé.
7.
Bien que le service de l'emploi succombe, il n'y a pas lieu de prélever des frais judiciaires (art. 66 al. 4 LTF; <ref-ruling> consid. 4.5 p. 642).

Le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Il n'est pas perçu de frais de justice.
3.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, et au Secrétariat d'Etat à l'économie (SECO).
Lucerne, le 16 avril 2014
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente: Leuzinger
La Greffière: Fretz Perrin